Panggilan fungsi rekursif. Algoritma rekursif dan rekursif

Untuk tidak menulis satu artikel besar, di mana terdapat banyak contoh rekursi dalam C++, saya akan menulis satu lagi contoh rekursi di sini. Pada umumnya, mereka yang memahami asas dan penggunaan rekursi langsung dalam fungsi mereka boleh melangkau bahan ini. Berikut ialah contoh penggunaan rekursi, seperti dalam artikel Functions in C++ for Beginners. Rekursi

Masalah 1 – Menggunakan rekursi, paparkan pemfaktoran nombor dari 1 hingga N
Menulis kod
=============================
TAHAP No 1 tulis program kosong
=============================

#termasuk

int utama()
{
sistem("cls");

getch();
pulangan 0;
}

Program kosong telah dibuat, saya rasa tidak perlu mengulas
TAHAP No. 2 kita tulis kita tulis fungsi rekursif itu sendiri
=========================================

#termasuk

//Fungsi rekursif kami
int fakta (int N )
{

//0! = 1, 1!=1, 2!=2, 3!=6... Kerana 2 nombor pertama adalah satu dan tidak dalam urutan yang ketat, kami memaksa titik ini dalam kod

jika n<2 return 1 ;
lain kembali n * fakta(n–1) //di sini fungsi memanggil dirinya sendiri

}

int utama()
{
sistem("cls");
cout<//Titik panggilan fungsi rekursif. Mencetak faktorial 10 pada skrin
getch();
pulangan 0;
}
ddd
============

Bahagian utama dalam program rekursi C++
kembali n * fakta(n–1)

Fungsi kami mengira semula untuk mendapatkan nilai sebelumnya. Nilai sebenar ialah parameter yang dihantar kepada n dari titik panggilan fungsi. Tujuan memanggil fungsi kami adalah untuk memanggilnya dari blok utama program. Dalam kes kami, kami memanggilnya daripada fungsi int utama()
Mengapa saya tidak menulis yang seterusnya, tetapi yang sebelumnya? Apabila nombor didarab, maka pertama 0 * 1 di sini ialah nilai semasa kami 1, dan sifar ialah nilai pengiraan sebelumnya. Ini adalah intipati keseluruhan rekursi, kami mengira nilai sekarang menggunakan yang sebelumnya, manakala nilai sebelumnya diperoleh dengan pengiraan yang sama. Pengkompil sendiri mengira nilai sebelumnya dan menyimpan nilai ini dalam ingatan. Apa yang perlu kita lakukan ialah memberi arahan. . Terima kasih kepada ciri penyusun ini, fungsi yang menghadapi arahan untuk memanggil dirinya sendiri (dalam kes kami fakta(n–1) )tidak menulis ganti parameter yang dihantar ke n untuk mengira fungsi. Parameter diserahkan kepada n ia kekal dalam ingatan. Dalam kes ini, kawasan memori lain ditakrifkan tambahan di mana fungsi rekursif kami melakukan pengiraan rekursif untuk mendapatkan hasil sebelumnya.

Semoga pengaturcara memaafkan saya atas penghakiman yang begitu rumit. Ini adalah lebih kurang bagaimana pemula melihat rekursi.

Saya harap blog C++ untuk pemula ini berguna kepada seseorang dan membantu seseorang memahami konsep asas fungsi rekursif dalam C++

Catatan. Dalam artikel ini, seperti dalam yang sebelumnya, saya melakukan pengiraan bukan dari 1 hingga N, tetapi kepada nilai yang dimasukkan ke dalam program. Intinya ialah saya tidak mahu menulis baris tambahan kod dan menganggap bahawa pengguna sudah mahir dalam memasukkan data dan memaparkannya pada skrin.

Hello Habrahabr!

Dalam artikel ini kita akan bercakap tentang masalah rekursi dan cara menyelesaikannya.

Secara ringkas tentang rekursi

Rekursi adalah fenomena yang agak biasa yang berlaku bukan sahaja dalam bidang sains, tetapi juga dalam kehidupan seharian. Contohnya, kesan Droste, segi tiga Sierpinski, dsb. Satu cara untuk melihat rekursi adalah dengan menghalakan kamera Web pada skrin monitor komputer, secara semula jadi, setelah menghidupkannya dahulu. Oleh itu, kamera akan merakam imej skrin komputer dan memaparkannya pada skrin ini, ia akan menjadi sesuatu seperti gelung tertutup. Akibatnya, kita akan melihat sesuatu yang serupa dengan terowong.

Dalam pengaturcaraan, rekursi berkait rapat dengan fungsi; lebih tepat lagi, ia adalah terima kasih kepada fungsi dalam pengaturcaraan bahawa terdapat perkara seperti rekursi atau fungsi rekursif. Secara ringkasnya, rekursi ialah takrifan sebahagian daripada fungsi (kaedah) melalui dirinya sendiri, iaitu fungsi yang memanggil dirinya, secara langsung (dalam badannya) atau secara tidak langsung (melalui fungsi lain).

Banyak yang telah diperkatakan tentang rekursi. Berikut adalah beberapa sumber yang baik:

Masalah rekursif dan rekursif. Bidang penggunaan rekursi

Diandaikan bahawa pembaca secara teorinya biasa dengan rekursi dan tahu apa itu. Dalam artikel ini kita akan memberi perhatian lebih kepada masalah rekursi.

Tugasan

Apabila mempelajari rekursi, cara yang paling berkesan untuk memahami rekursi ialah menyelesaikan masalah.

Bagaimana untuk menyelesaikan masalah rekursi?

Pertama sekali, anda perlu memahami bahawa rekursi adalah sejenis keterlaluan. Secara umumnya, semua yang diselesaikan secara berulang boleh diselesaikan secara rekursif, iaitu, menggunakan fungsi rekursif.

daripada rangkaian

Sebarang algoritma yang dilaksanakan dalam bentuk rekursif boleh ditulis semula dalam bentuk lelaran dan sebaliknya. Persoalannya tetap sama ada ini perlu dan sejauh mana ia akan berkesan.

Hujah-hujah berikut boleh diberikan untuk membenarkan perkara ini.

Sebagai permulaan, kita boleh mengingati definisi rekursi dan lelaran. Rekursi ialah cara mengatur pemprosesan data di mana program memanggil dirinya secara langsung atau dengan bantuan program lain. Lelaran ialah cara mengatur pemprosesan data di mana tindakan tertentu diulang berkali-kali tanpa membawa kepada panggilan program rekursif.

Selepas itu kita boleh membuat kesimpulan bahawa mereka boleh ditukar ganti, tetapi tidak selalu dengan kos yang sama dari segi sumber dan kelajuan. Untuk mewajarkan ini, kita boleh memberikan contoh berikut: terdapat fungsi di mana, untuk mengatur algoritma tertentu, terdapat gelung yang melakukan urutan tindakan bergantung pada nilai semasa pembilang (ia mungkin tidak bergantung pada ia). Oleh kerana terdapat kitaran, ini bermakna badan mengulangi urutan tindakan - lelaran kitaran. Anda boleh mengalihkan operasi ke dalam subrutin yang berasingan dan memberikannya nilai pembilang, jika ada. Setelah selesai melaksanakan subrutin, kami menyemak syarat untuk melaksanakan gelung, dan jika ia benar, kami meneruskan panggilan baharu kepada subrutin; jika ia salah, kami melengkapkan pelaksanaan. Kerana Kami meletakkan semua kandungan gelung dalam subrutin, yang bermaksud bahawa syarat untuk melaksanakan gelung juga diletakkan dalam subrutin, dan ia boleh diperolehi melalui nilai pulangan fungsi, parameter yang diluluskan melalui rujukan atau penunjuk kepada subrutin. , serta pembolehubah global. Selanjutnya, adalah mudah untuk menunjukkan bahawa panggilan ke subrutin tertentu daripada gelung boleh ditukar dengan mudah menjadi panggilan atau bukan panggilan (memulangkan nilai atau hanya menyelesaikan kerja) subrutin daripada dirinya sendiri, berpandukan beberapa syarat (yang sebelum ini berada dalam keadaan gelung). Sekarang, jika anda melihat program abstrak kami, ia secara kasarnya kelihatan seperti menghantar nilai kepada subrutin dan menggunakannya, yang subrutin itu akan berubah apabila ia selesai, i.e. kami menggantikan gelung berulang dengan panggilan rekursif kepada subrutin untuk menyelesaikan algoritma yang diberikan.

Tugas membawa rekursi kepada pendekatan berulang adalah simetri.

Untuk meringkaskan, kita boleh menyatakan pemikiran berikut: untuk setiap pendekatan terdapat kelas tugasnya sendiri, yang ditentukan oleh keperluan khusus untuk tugas tertentu.

Anda boleh mengetahui lebih lanjut mengenai perkara ini

Sama seperti penghitungan (kitaran), rekursi mesti mempunyai keadaan berhenti - Kes asas (jika tidak, sama seperti kitaran, rekursi akan berfungsi selama-lamanya - tidak terhingga). Keadaan ini ialah kes yang berlaku rekursi (langkah rekursi). Pada setiap langkah, fungsi rekursif dipanggil sehingga panggilan seterusnya mencetuskan keadaan asas dan rekursi berhenti (atau sebaliknya, kembali ke panggilan fungsi terakhir). Keseluruhan penyelesaian datang kepada menyelesaikan kes asas. Dalam kes di mana fungsi rekursif dipanggil untuk menyelesaikan masalah yang kompleks (bukan kes asas), beberapa panggilan atau langkah rekursif dilakukan untuk mengurangkan masalah kepada yang lebih mudah. Dan seterusnya sehingga kita mendapat penyelesaian asas.

Jadi fungsi rekursif terdiri daripada

Keadaan Berhenti atau Kes Asas
Keadaan penerusan atau langkah rekursi ialah satu cara untuk mengurangkan masalah kepada yang lebih mudah.

Mari kita lihat ini menggunakan contoh mencari faktorial:

Penyelesaian kelas awam ( public static int recursion(int n) ( // keadaan keluar // Kes asas // bila hendak berhenti mengulang rekursi? jika (n == 1) ( return 1; ) // Langkah rekursif / keadaan rekursif kembali rekursi(n - 1) * n; ) public static void main(String args) ( System.out.println(recursion(5)); // panggil fungsi rekursif ) )

Di sini syarat asas ialah keadaan apabila n=1. Oleh kerana kita tahu bahawa 1!=1 dan untuk mengira 1! kita tidak perlukan apa-apa. Untuk mengira 2! kita boleh menggunakan 1!, i.e. 2!=1!*2. Untuk mengira 3! kita perlukan 2!*3... Untuk mengira n! kita perlukan (n-1)!*n. Ini adalah langkah rekursi. Dengan kata lain, untuk mendapatkan nilai faktor bagi suatu nombor n, sudah cukup untuk mendarabkan nilai faktor bagi nombor sebelumnya dengan n.

Tag:

rekursi
tugasan
java

Tambah tag

Rekursi ialah apabila subrutin memanggil dirinya sendiri. Apabila berhadapan dengan reka bentuk algoritmik sedemikian buat kali pertama, kebanyakan orang mengalami kesukaran tertentu, tetapi dengan sedikit latihan, rekursi akan menjadi alat yang mudah difahami dan sangat berguna dalam senjata pengaturcaraan anda.

1. Intipati rekursi

Prosedur atau fungsi mungkin mengandungi panggilan ke prosedur atau fungsi lain. Prosedur itu juga boleh memanggil dirinya sendiri. Tiada paradoks di sini - komputer hanya melaksanakan perintah yang ditemuinya secara berurutan dalam program dan, jika ia menghadapi panggilan prosedur, ia hanya mula melaksanakan prosedur ini. Tidak kira prosedur apa yang memberi arahan untuk melakukan ini.

Contoh prosedur rekursif:

Prosedur Rec(a: integer); mulakan jika a>

Mari kita pertimbangkan apa yang berlaku jika panggilan, sebagai contoh, borang Rec(3) dibuat dalam program utama. Di bawah ialah carta alir yang menunjukkan urutan pelaksanaan pernyataan.

nasi. 1. Gambar rajah blok prosedur rekursif.

Prosedur Rec dipanggil dengan parameter a = 3. Ia mengandungi panggilan ke prosedur Rec dengan parameter a = 2. Panggilan sebelumnya belum selesai, jadi anda boleh bayangkan bahawa prosedur lain dibuat dan yang pertama tidak menyelesaikan kerjanya sehingga ia selesai. Proses panggilan tamat apabila parameter a = 0. Pada ketika ini, 4 kejadian prosedur dilaksanakan secara serentak. Bilangan prosedur yang dilakukan secara serentak dipanggil kedalaman rekursi.

Prosedur keempat yang dipanggil (Rec(0)) akan mencetak nombor 0 dan menyelesaikan kerjanya. Selepas ini, kawalan kembali kepada prosedur yang memanggilnya (Rec(1)) dan nombor 1 dicetak. Dan seterusnya sehingga semua prosedur selesai. Panggilan asal akan mencetak empat nombor: 0, 1, 2, 3.

Satu lagi imej visual tentang apa yang berlaku ditunjukkan dalam Rajah. 2.

nasi. 2. Melaksanakan prosedur Rec dengan parameter 3 terdiri daripada melaksanakan prosedur Rec dengan parameter 2 dan mencetak nombor 3. Seterusnya, melaksanakan prosedur Rec dengan parameter 2 terdiri daripada melaksanakan prosedur Rec dengan parameter 1 dan mencetak nombor 2. Dll .

Sebagai latihan anda sendiri, pertimbangkan perkara yang berlaku apabila anda memanggil Rec(4). Pertimbangkan juga perkara yang akan berlaku jika anda memanggil prosedur Rec2(4) di bawah, dengan operator diterbalikkan.

Prosedur Rec2(a: integer); mula writeln(a); jika a>0 maka Rec2(a-1); akhir;

Sila ambil perhatian bahawa dalam contoh ini panggilan rekursif berada di dalam pernyataan bersyarat. Ini adalah syarat yang perlu untuk rekursi kekal. Juga ambil perhatian bahawa prosedur memanggil dirinya sendiri dengan parameter yang berbeza daripada yang ia dipanggil. Jika prosedur tidak menggunakan pembolehubah global, maka ini juga perlu supaya rekursi tidak berterusan selama-lamanya.

Skim yang sedikit lebih kompleks mungkin: fungsi A memanggil fungsi B, yang seterusnya memanggil A. Ini dipanggil rekursi kompleks. Ternyata prosedur yang diterangkan terlebih dahulu mesti memanggil prosedur yang belum diterangkan. Untuk ini menjadi mungkin, anda perlu menggunakan .

Prosedur A(n: integer); (Keterangan ke hadapan (pengepala) prosedur pertama) prosedur B(n: integer); (Penerangan ke hadapan bagi prosedur kedua) prosedur A(n: integer); (Penerangan penuh prosedur A) mula writeln(n); B(n-1); akhir; prosedur B(n: integer); (Penerangan penuh prosedur B) mula writeln(n); jika n

Pengisytiharan ke hadapan prosedur B membolehkan ia dipanggil daripada prosedur A. Pengisytiharan ke hadapan prosedur A tidak diperlukan dalam contoh ini dan ditambah atas sebab estetik.

Jika rekursi biasa boleh disamakan dengan ouroboros (Rajah 3), maka imej pengulangan kompleks boleh diambil dari puisi kanak-kanak yang terkenal, di mana "Serigala ketakutan dan makan antara satu sama lain." Bayangkan dua serigala makan antara satu sama lain dan anda akan memahami rekursi yang kompleks.

nasi. 3. Ouroboros - ular yang memakan ekornya sendiri. Melukis daripada risalah alkimia "Synosius" oleh Theodore Pelecanos (1478).

nasi. 4. Rekursi kompleks.

3. Mensimulasikan gelung menggunakan rekursi

Jika prosedur memanggil dirinya sendiri, ia pada asasnya menyebabkan arahan yang terkandung di dalamnya dilaksanakan semula, serupa dengan gelung. Sesetengah bahasa pengaturcaraan tidak mengandungi binaan gelung sama sekali, meninggalkan pengaturcara untuk mengatur ulangan menggunakan rekursi (contohnya, Prolog, di mana rekursi ialah teknik pengaturcaraan asas).

Sebagai contoh, mari kita simulasi operasi gelung for. Untuk melakukan ini, kita memerlukan pembolehubah kaunter langkah, yang boleh dilaksanakan, sebagai contoh, sebagai parameter prosedur.

Contoh 1.

Prosedur LoopImitation(i, n: integer); (Parameter pertama ialah pembilang langkah, parameter kedua ialah jumlah bilangan langkah) mula writeln("Hello N ", i); //Berikut adalah sebarang arahan yang akan diulang jika i

Hasil daripada panggilan borang LoopImitation(1, 10) akan menjadi pelaksanaan arahan sepuluh kali dengan pembilang berubah daripada 1 kepada 10. Dalam dalam kes ini akan dicetak:

Salam N 1
Salam N 2
…
Salam N 10

Secara umum, tidak sukar untuk melihat bahawa parameter prosedur adalah had untuk menukar nilai pembilang.

Anda boleh menukar panggilan rekursif dan arahan untuk diulang, seperti dalam contoh berikut.

Contoh 2.

Prosedur LoopImitation2(i, n: integer); mulakan jika saya

Dalam kes ini, panggilan prosedur rekursif akan berlaku sebelum arahan mula dilaksanakan. Contoh baru prosedur juga akan, pertama sekali, memanggil contoh lain, dan seterusnya, sehingga kita mencapai nilai maksimum kaunter. Hanya selepas ini prosedur terakhir yang dipanggil akan melaksanakan arahannya, kemudian yang kedua hingga terakhir akan melaksanakan arahannya, dsb. Hasil daripada memanggil LoopImitation2(1, 10) adalah untuk mencetak salam dalam susunan terbalik:

Salam N 10
…
Salam N 1

Jika kita bayangkan rangkaian prosedur yang dipanggil secara rekursif, maka dalam contoh 1 kita melaluinya daripada prosedur yang dipanggil lebih awal kepada prosedur yang kemudian. Dalam contoh 2, sebaliknya, dari kemudian ke lebih awal.

Akhir sekali, panggilan rekursif boleh diletakkan di antara dua blok arahan. Sebagai contoh:

Prosedur LoopImitation3(i, n: integer); mula writeln("Hello N", i); (Blok arahan pertama mungkin terdapat di sini) jika i

Di sini, arahan dari blok pertama mula-mula dilaksanakan secara berurutan, kemudian arahan dari blok kedua dilaksanakan dalam susunan terbalik. Apabila memanggil LoopImitation3(1, 10) kita mendapat:

Salam N 1
…
Salam N 10
Salam N 10
…
Salam N 1

Ia akan mengambil dua gelung untuk melakukan perkara yang sama tanpa rekursi.

Anda boleh mengambil kesempatan daripada fakta bahawa pelaksanaan bahagian prosedur yang sama dijarakkan mengikut masa. Sebagai contoh:

Contoh 3: Menukar nombor kepada perduaan.

Mendapatkan digit nombor binari, seperti yang diketahui, berlaku dengan membahagikan dengan baki dengan asas sistem nombor 2. Jika terdapat nombor, maka digit terakhirnya dalam perwakilan binarinya adalah sama dengan

Mengambil keseluruhan bahagian pembahagian dengan 2:

kita mendapat nombor yang mempunyai perwakilan binari yang sama, tetapi tanpa digit terakhir. Oleh itu, cukup untuk mengulangi dua operasi di atas sehingga medan pembahagian seterusnya menerima bahagian integer bersamaan dengan 0. Tanpa rekursi ia akan kelihatan seperti ini:

Walaupun x>0 bermula c:=x mod 2; x:=x div 2; tulis(c); akhir;

Masalahnya di sini ialah digit bagi perwakilan binari dikira dalam susunan terbalik (terkini dahulu). Untuk mencetak nombor dalam bentuk biasa, anda perlu mengingati semua nombor dalam elemen tatasusunan dan mencetaknya dalam gelung yang berasingan.

Menggunakan rekursi, tidak sukar untuk mencapai output dalam susunan yang betul tanpa tatasusunan dan gelung kedua. Iaitu:

Perwakilan Perduaan Prosedur(x: integer); var c, x: integer; mulakan (Blok pertama. Dilaksanakan mengikut urutan panggilan prosedur) c:= x mod 2; x:= x div 2; (Panggilan rekursif) jika x>0 maka BinaryRepresentation(x); (Blok kedua. Dilaksanakan dalam susunan terbalik) tulis(c); akhir;

Secara umumnya, kami tidak menerima sebarang kemenangan. Digit perwakilan binari disimpan dalam pembolehubah tempatan, yang berbeza untuk setiap contoh larian prosedur rekursif. Iaitu, tidak mungkin untuk menyimpan memori. Sebaliknya, kami membazirkan memori tambahan dengan menyimpan banyak pembolehubah tempatan x. Walau bagaimanapun, penyelesaian ini kelihatan cantik kepada saya.

4. Hubungan berulang. Rekursi dan Lelaran

Urutan vektor dikatakan diberikan oleh hubungan berulang jika vektor awal dan kebergantungan fungsi vektor berikutnya pada sebelumnya diberikan

Contoh mudah kuantiti yang dikira menggunakan hubungan berulang ialah faktorial

Faktorial seterusnya boleh dikira dari yang sebelumnya sebagai:

Dengan memperkenalkan notasi , kami memperoleh hubungan:

Vektor daripada formula (1) boleh ditafsirkan sebagai set nilai pembolehubah. Kemudian pengiraan unsur yang diperlukan bagi jujukan akan terdiri daripada pengemaskinian berulang nilainya. Khususnya untuk faktorial:

X:= 1; untuk i:= 2 hingga n lakukan x:= x * i; writeln(x);

Setiap kemas kini tersebut (x:= x * i) dipanggil lelaran, dan proses mengulangi lelaran ialah lelaran.

Walau bagaimanapun, mari kita ambil perhatian bahawa hubungan (1) ialah definisi rekursif semata-mata bagi jujukan dan pengiraan unsur ke-n sebenarnya adalah pengambilan berulang fungsi f daripada dirinya sendiri:

Khususnya, untuk faktorial seseorang boleh menulis:

Fungsi Faktorial(n: integer): integer; mulakan jika n > 1 maka Factorial:= n * Factorial(n-1) else Factorial:= 1; akhir;

Perlu difahami bahawa fungsi panggilan memerlukan beberapa overhed tambahan, jadi pilihan pertama untuk mengira faktorial akan menjadi lebih cepat sedikit. Secara umum, penyelesaian berulang berfungsi lebih cepat daripada penyelesaian rekursif.

Sebelum beralih kepada situasi di mana rekursi berguna, mari lihat satu lagi contoh yang tidak sepatutnya digunakan.

Mari kita pertimbangkan kes khas hubungan berulang, apabila nilai seterusnya dalam urutan tidak bergantung pada satu, tetapi pada beberapa nilai sebelumnya sekaligus. Contohnya ialah jujukan Fibonacci yang terkenal, di mana setiap elemen seterusnya ialah jumlah dua sebelumnya:

Dengan pendekatan "depan", anda boleh menulis:

Fungsi Fib(n: integer): integer; mulakan jika n > 1 maka Fib:= Fib(n-1) + Fib(n-2) else Fib:= 1; akhir;

Setiap panggilan Fib mencipta dua salinan dirinya sendiri, setiap salinan mencipta dua lagi, dan seterusnya. Bilangan operasi meningkat dengan bilangan n secara eksponen, walaupun dengan penyelesaian lelaran linear in n bilangan operasi.

Sebenarnya, contoh di atas tidak mengajar kita BILA rekursi tidak boleh digunakan, jika tidak BAGAIMANA ia tidak sepatutnya digunakan. Lagipun, jika terdapat penyelesaian lelaran cepat (berasaskan gelung), maka gelung yang sama boleh dilaksanakan menggunakan prosedur atau fungsi rekursif. Sebagai contoh:

// x1, x2 – keadaan awal (1, 1) // n – nombor fungsi nombor Fibonacci yang diperlukan Fib(x1, x2, n: integer): integer; var x3: integer; mulakan jika n > 1 kemudian mulakan x3:= x2 + x1; x1:= x2; x2:= x3; Fib:= Fib(x1, x2, n-1); tamat lain Fib:= x2; akhir;

Namun, penyelesaian berulang adalah lebih baik. Persoalannya, bilakah rekursi harus digunakan dalam kes ini?

mana-mana prosedur rekursif dan fungsi yang mengandungi hanya satu panggilan rekursif kepada diri mereka sendiri mudah digantikan dengan gelung berulang. Untuk mendapatkan sesuatu yang tidak mempunyai rakan bukan rekursif yang mudah, anda perlu menggunakan prosedur dan fungsi yang memanggil diri mereka dua kali atau lebih. Dalam kes ini, set prosedur yang dipanggil tidak lagi membentuk rantai, seperti dalam Rajah. 1, tetapi seluruh pokok. Terdapat pelbagai kelas masalah apabila proses pengkomputeran harus disusun dengan cara ini. Hanya untuk mereka, rekursi akan menjadi yang paling mudah dan secara semula jadi penyelesaian.

5. Pokok

Asas teori untuk fungsi rekursif yang memanggil diri mereka lebih daripada sekali ialah cabang matematik diskret yang mengkaji pokok.

5.1. Definisi asas. Cara untuk menggambarkan pokok

Definisi: kita akan panggil set terhingga T, yang terdiri daripada satu atau lebih nod seperti:
a) Terdapat satu nod khas yang dipanggil akar pokok ini.
b) Nod yang selebihnya (tidak termasuk akar) terkandung dalam subset berpisah berpasangan, setiap satunya adalah pokok. Pokok dipanggil pokok pokok pokok ini.

Definisi ini adalah rekursif. Ringkasnya, pokok ialah satu set yang terdiri daripada akar dan pokok kecil yang melekat padanya, yang juga merupakan pokok. Pokok ditakrifkan melalui dirinya sendiri. Namun begitu takrifan ini masuk akal, kerana rekursi adalah terhad. Setiap subpokok mengandungi lebih sedikit nod daripada pokok yang mengandunginya. Akhirnya, kita sampai ke subpokok yang mengandungi hanya satu nod, dan ini sudah jelas apa itu.

nasi. 3. Pokok.

Dalam Rajah. Rajah 3 menunjukkan sebatang pokok dengan tujuh nod. Walaupun pokok biasa tumbuh dari bawah ke atas, adalah kebiasaan untuk menariknya sebaliknya. Apabila melukis gambar rajah dengan tangan, kaedah ini jelas lebih mudah. Kerana ketidakkonsistenan ini, kekeliruan kadangkala timbul apabila satu nod dikatakan berada di atas atau di bawah yang lain. Atas sebab ini, adalah lebih mudah untuk menggunakan istilah yang digunakan semasa menerangkan pokok keluarga, memanggil nod lebih dekat kepada nenek moyang akar dan keturunan nod yang lebih jauh.

Sebatang pokok boleh digambarkan secara grafik dalam beberapa cara lain. Sebahagian daripadanya ditunjukkan dalam Rajah. 4. Mengikut definisi, pokok ialah sistem set bersarang, di mana set ini sama ada tidak bersilang atau terkandung sepenuhnya antara satu sama lain. Set sedemikian boleh digambarkan sebagai kawasan pada satah (Rajah 4a). Dalam Rajah. 4b, set bersarang tidak terletak pada satah, tetapi dipanjangkan menjadi satu baris. nasi. 4b juga boleh dilihat sebagai gambar rajah beberapa formula algebra yang mengandungi kurungan bersarang. nasi. 4b memberikan satu lagi cara popular imej struktur pokok dalam bentuk senarai berperingkat.

nasi. 4. Cara lain untuk menggambarkan struktur pokok: (a) set bersarang; (b) kurungan bersarang; (c) senarai konsesi.

Senarai berperingkat mempunyai persamaan yang jelas dengan kaedah pemformatan kod program. Sesungguhnya, atur cara yang ditulis dalam rangka paradigma pengaturcaraan berstruktur boleh diwakili sebagai pokok yang terdiri daripada struktur bersarang.

Anda juga boleh melukis analogi antara senarai langkan dan penampilan jadual kandungan dalam buku di mana bahagian mengandungi subseksyen, yang seterusnya mengandungi subseksyen, dsb. Cara tradisional Penomboran bahagian tersebut (bahagian 1, subseksyen 1.1 dan 1.2, subseksyen 1.1.2, dsb.) dipanggil sistem perpuluhan Dewey. Digunakan pada pokok dalam Rajah. 3 dan 4 sistem ini akan memberikan:

1. A; 1.1B; 1.2 C; 1.2.1 D; 1.2.2 E; 1.2.3 F; 1.2.3.1 G;

5.2. pokok yang lalu lalang

Dalam semua algoritma yang berkaitan dengan struktur pokok, idea yang sama selalu muncul, iaitu idea berlalu atau lintasan pokok. Ini ialah cara melawati nod pokok di mana setiap nod dilalui tepat sekali. Ini menghasilkan susunan linear nod pokok. Khususnya, terdapat tiga cara: anda boleh melalui nod dalam susunan hadapan, belakang dan akhir.

Algoritma lintasan hadapan:

Sampai ke akar umbi
Pergi melalui semua subpokok dari kiri ke kanan dalam urutan langsung.

Algoritma ini adalah rekursif, kerana traversal pokok mengandungi traversal subtrees, dan mereka, seterusnya, dilalui menggunakan algoritma yang sama.

Khususnya, untuk pokok dalam Rajah. 3 dan 4, traversal terus memberikan urutan nod: A, B, C, D, E, F, G.

Urutan yang terhasil sepadan dengan penghitungan nod dari kiri ke kanan berurutan apabila mewakili pokok menggunakan kurungan bersarang dan dalam sistem perpuluhan Dewey, serta petikan atas ke bawah apabila dibentangkan dalam bentuk senarai berperingkat.

Apabila melaksanakan algoritma ini dalam bahasa pengaturcaraan, memukul akar sepadan dengan prosedur atau fungsi yang melakukan beberapa tindakan, dan melalui subpokok sepadan dengan panggilan rekursif kepada dirinya sendiri. Khususnya, untuk pokok binari (di mana setiap nod mempunyai paling banyak dua subpohon), prosedur yang sepadan akan kelihatan seperti ini:

// Preorder Traversal – Nama Inggeris untuk prosedur pesanan terus PreorderTraversal((Arguments)); mulakan //Melalui akar DoSomething((Arguments)); //Peralihan subpokok kiri jika (Terdapat subpokok kiri) kemudian PreorderTransversal((Argumen 2)); //Peralihan subtree kanan jika (Terdapat subtree kanan) kemudian PreorderTransversal((Argumen 3)); akhir;

Iaitu, pertama prosedur melakukan semua tindakan, dan hanya kemudian semua panggilan rekursif berlaku.

Algoritma lintasan terbalik:

Pergi melalui subpokok kiri,
Sampai ke akar umbi
Pergi melalui subpokok seterusnya di sebelah kiri.
Sampai ke akar umbi
dan lain-lain sehingga subpokok paling kanan dilalui.

Iaitu, semua subpohon dilalui dari kiri ke kanan, dan kembali ke akar terletak di antara traversal ini. Untuk pokok dalam Rajah. 3 dan 4 ini memberikan urutan nod: B, A, D, C, E, G, F.

Dalam prosedur rekursif yang sepadan, tindakan akan ditempatkan di ruang antara panggilan rekursif. Khusus untuk pokok binari:

// Inorder Traversal – Nama Inggeris untuk prosedur terbalik InorderTraversal((Arguments)); mulakan //Menelusuri subpokok kiri jika (subpokok kiri wujud) kemudian InorderTraversal((Argumen 2)); //Melalui akar DoSomething((Arguments)); //Traverse subtree kanan jika (subtree kanan wujud) kemudian InorderTraversal((Arguments 3)); akhir;

Algoritma lintasan pesanan akhir:

Pergi melalui semua subpokok dari kiri ke kanan,
Sampai ke akar umbi.

Untuk pokok dalam Rajah. 3 dan 4 ini akan memberikan urutan nod: B, D, E, G, F, C, A.

Dalam prosedur rekursif yang sepadan, tindakan akan ditemui selepas panggilan rekursif. Khusus untuk pokok binari:

// Postorder Traversal – Nama Inggeris untuk prosedur pesanan akhir PostorderTraversal((Arguments)); mulakan //Menelusuri subpokok kiri jika (Terdapat subpokok kiri) kemudian PostorderTraversal((Argumen 2)); //Merentasi subpokok kanan jika (subpokok kanan wujud) kemudian PostorderTraversal((Argumen 3)); //Melalui akar DoSomething((Arguments)); akhir;

5.3. Perwakilan pokok dalam ingatan komputer

Jika sesetengah maklumat terletak dalam nod pokok, maka struktur data dinamik yang sesuai boleh digunakan untuk menyimpannya. Dalam Pascal ini dilakukan menggunakan jenis berubah-ubah rekod yang mengandungi penunjuk kepada subpokok daripada jenis yang sama. Sebagai contoh, pokok binari di mana setiap nod mengandungi integer boleh disimpan menggunakan pembolehubah jenis PTree, yang diterangkan di bawah:

Taip PTree = ^TTree; TTree = rekod Inf: integer; LeftSubTree, RightSubTree: PTree; akhir;

Setiap nod mempunyai jenis PTree. Ini ialah penunjuk, bermakna setiap nod mesti dibuat dengan memanggil prosedur Baharu padanya. Jika nod ialah nod daun, maka medan LeftSubTree dan RightSubTreenya diberikan nilai tiada. Jika tidak, nod LeftSubTree dan RightSubTree juga dicipta oleh prosedur Baharu.

Satu rekod sedemikian ditunjukkan secara skematik dalam Rajah. 5.

nasi. 5. Perwakilan skematik rekod jenis TTree. Rekod mempunyai tiga medan: Inf – nombor, LeftSubTree dan RightSubTree – penunjuk kepada rekod jenis TTree yang sama.

Contoh pokok yang terdiri daripada rekod tersebut ditunjukkan dalam Rajah 6.

nasi. 6. Pokok yang terdiri daripada rekod jenis TTree. Setiap entri menyimpan nombor dan dua petunjuk yang boleh mengandungi sama ada tiada, atau alamat rekod lain daripada jenis yang sama.

Jika sebelum ini anda tidak pernah bekerja dengan struktur yang terdiri daripada rekod yang mengandungi pautan kepada rekod jenis yang sama, kami mengesyorkan agar anda membiasakan diri dengan bahan mengenainya.

6. Contoh algoritma rekursif

6.1. Melukis pokok

Mari kita pertimbangkan algoritma untuk melukis pokok yang ditunjukkan dalam Rajah. 6. Jika setiap baris dianggap sebagai nod, maka imej ini memenuhi sepenuhnya definisi pokok yang diberikan dalam bahagian sebelumnya.

nasi. 6. Pokok.

Prosedur rekursif jelas akan melukis satu baris (batang sehingga ke cawangan pertama), dan kemudian memanggil dirinya sendiri untuk melukis dua subpohon. Subpohon berbeza daripada pokok yang mengandunginya dalam koordinat titik permulaannya, sudut putaran, panjang batang dan bilangan cabang yang dikandungnya (kurang satu). Semua perbezaan ini harus dijadikan parameter bagi prosedur rekursif.

Contoh prosedur sedemikian, yang ditulis dalam Delphi, dibentangkan di bawah:

Pokok Prosedur(Kanvas: TCanvas; //Kanvas di mana pokok itu akan dilukis x,y: dilanjutkan; //Koordinat akar Sudut: dilanjutkan; //Sudut di mana pokok itu tumbuh Panjang Batang: dilanjutkan; //Panjang batang n: integer //Bilangan cawangan (berapa banyak lagi //panggilan rekursif kekal)); var x2, y2: dilanjutkan; //Hujung batang (titik cawangan) bermula x2:= x + Panjang Batang * cos(Sudut); y2:= y - Panjang Batang * sin(Sudut); Canvas.MoveTo(bulat(x), bulat(y)); Canvas.LineTo(bulat(x2), bulat(y2)); jika n > 1 maka mulakan Tree(Kanvas, x2, y2, Angle+Pi/4, 0.55*TrunkLength, n-1); Pokok(Kanvas, x2, y2, Sudut-Pi/4, 0.55*Panjang Batang, n-1); akhir; akhir;

Untuk mendapatkan Rajah. 6 prosedur ini dipanggil dengan parameter berikut:

Pokok(Imej1.Kanvas, 175, 325, Pi/2, 120, 15);

Ambil perhatian bahawa lukisan dijalankan sebelum panggilan rekursif, iaitu, pokok dilukis dalam susunan langsung.

6.2. Menara Hanoi

Menurut legenda di Kuil Besar Banaras, di bawah katedral, menandakan tengah-tengah dunia, terdapat cakera gangsa di mana 3 batang berlian dipasang, satu hasta tinggi dan tebal seperti lebah. Pada masa dahulu, pada permulaan masa, para bhikkhu biara ini melakukan kesalahan di hadapan dewa Brahma. Marah, Brahma mendirikan tiga batang tinggi dan meletakkan 64 cakera emas tulen pada salah satu daripadanya, supaya setiap cakera yang lebih kecil diletakkan pada cakera yang lebih besar. Sebaik sahaja kesemua 64 cakera dipindahkan dari batang yang diletakkan Tuhan Brahma ketika mencipta dunia, ke batang lain, menara bersama kuil akan bertukar menjadi debu dan dunia akan binasa di bawah bunyi petir.
Proses memerlukan itu cakera yang lebih besar tidak pernah mendapati diri saya lebih daripada sesuatu yang kurang. Para bhikkhu berada dalam dilema: dalam urutan apakah mereka harus melakukan pergeseran? Ia dikehendaki menyediakan mereka dengan perisian untuk mengira jujukan ini.

Secara bebas daripada Brahma, teka-teki ini telah dicadangkan pada akhir abad ke-19 oleh ahli matematik Perancis Edouard Lucas. Versi yang dijual biasanya menggunakan 7-8 cakera (Gamb. 7).

nasi. 7. Teka-teki "Menara Hanoi".

Mari kita anggap bahawa ada penyelesaian untuk n-1 cakera. Kemudian untuk peralihan n cakera, teruskan seperti berikut:

1) Anjakan n-1 cakera.
2) Anjakan n cakera ke ke baki pin percuma.
3) Kami mengalihkan timbunan dari n-1 cakera diterima dalam titik (1) di atas n cakera ke-.

Kerana untuk kes itu n= 1 algoritma penyusunan semula adalah jelas, maka dengan induksi, menggunakan tindakan (1) – (3), kita boleh menyusun semula bilangan cakera yang sewenang-wenangnya.

Mari buat prosedur rekursif yang mencetak keseluruhan urutan penyusunan semula untuk bilangan cakera tertentu. Setiap kali prosedur sedemikian dipanggil, ia mesti mencetak maklumat tentang satu anjakan (dari titik 2 algoritma). Untuk penyusunan semula dari titik (1) dan (3), prosedur akan memanggil dirinya sendiri dengan bilangan cakera dikurangkan sebanyak satu.

//n – bilangan cakera //a, b, c – nombor pin. Peralihan dilakukan dari pin a, //ke pin b dengan pin tambahan c. prosedur Hanoi(n, a, b, c: integer); mulakan jika n > 1 kemudian mulakan Hanoi(n-1, a, c, b); writeln(a, " -> ", b); Hanoi(n-1, c, b, a); end else writeln(a, " -> ", b); akhir;

Ambil perhatian bahawa set prosedur yang dipanggil secara rekursif dalam kes ini membentuk pokok yang dilalui dalam susunan terbalik.

6.3. Menghuraikan ungkapan aritmetik

Tugas penghuraian adalah untuk mengira nilai ungkapan menggunakan rentetan sedia ada yang mengandungi ungkapan aritmetik dan nilai pembolehubah yang diketahui termasuk di dalamnya.

Proses pengiraan ungkapan aritmetik boleh diwakili sebagai pokok binari. Sesungguhnya, setiap operator aritmetik (+, –, *, /) memerlukan dua operan, yang juga akan menjadi ungkapan aritmetik dan, dengan itu, boleh dianggap sebagai subpokok. nasi. Rajah 8 menunjukkan contoh pokok yang sepadan dengan ungkapan:

nasi. 8. Pokok sintaks yang sepadan ungkapan aritmetik (6).

Dalam pokok sedemikian, nod akhir akan sentiasa berubah-ubah (di sini x) atau pemalar berangka, dan semua nod dalaman akan mengandungi operator aritmetik. Untuk melaksanakan pengendali, anda mesti menilai dahulu operannya. Oleh itu, pokok dalam rajah itu harus dilalui dalam susunan terminal. Urutan nod yang sepadan

dipanggil terbalik notasi Poland ungkapan aritmetik.

Apabila membina pokok sintaks, anda harus memberi perhatian kepada ciri seterusnya. Jika, sebagai contoh, terdapat ungkapan

dan kita akan membaca operasi tambah dan tolak dari kiri ke kanan, maka pokok sintaks yang betul akan mengandungi tolak dan bukannya tambah (Rajah 9a). Pada dasarnya, pokok ini sepadan dengan ungkapan. Anda boleh membuat penciptaan pokok lebih mudah jika anda menganalisis ungkapan (8) secara terbalik, dari kanan ke kiri. Dalam kes ini, hasilnya adalah pokok dengan Rajah. 9b, bersamaan dengan pokok 8a, tetapi tidak memerlukan penggantian tanda.

Begitu juga, dari kanan ke kiri, anda perlu menganalisis ungkapan yang mengandungi operator darab dan bahagi.

nasi. 9. Pokok sintaks untuk ekspresi a – b + c apabila membaca dari kiri ke kanan (a) dan dari kanan ke kiri (b).

Pendekatan ini tidak menghapuskan rekursi sepenuhnya. Walau bagaimanapun, ia membolehkan anda mengehadkan diri anda kepada hanya satu panggilan ke prosedur rekursif, yang mungkin mencukupi jika motifnya adalah untuk memaksimumkan prestasi.

7.3. Menentukan nod pokok dengan nombornya

Idea pendekatan ini adalah untuk menggantikan panggilan rekursif dengan gelung mudah yang akan dilaksanakan seberapa banyak kali terdapat nod dalam pepohon yang dibentuk oleh prosedur rekursif. Apa sebenarnya yang akan dilakukan pada setiap langkah harus ditentukan oleh nombor langkah. Padankan nombor langkah dan tindakan yang perlu– tugas itu tidak remeh dan dalam setiap kes ia perlu diselesaikan secara berasingan.

Sebagai contoh, katakan anda mahu lakukan k gelung bersarang n langkah dalam setiap:

Untuk i1:= 0 hingga n-1 lakukan untuk i2:= 0 hingga n-1 lakukan untuk i3:= 0 hingga n-1 lakukan …

Jika k tidak diketahui terlebih dahulu, adalah mustahil untuk menulisnya secara eksplisit, seperti yang ditunjukkan di atas. Menggunakan teknik yang ditunjukkan dalam Bahagian 6.5, anda boleh mendapatkan bilangan gelung bersarang yang diperlukan menggunakan prosedur rekursif:

Prosedur NestedCycles(Indeks: tatasusunan integer; n, k, kedalaman: integer); var i: integer; bermula jika kedalaman

Untuk menghilangkan rekursi dan mengurangkan segala-galanya kepada satu kitaran, ambil perhatian bahawa jika anda menomborkan langkah-langkah dalam sistem nombor radix n, maka setiap langkah mempunyai nombor yang terdiri daripada nombor i1, i2, i3, ... atau nilai yang sepadan daripada tatasusunan Indeks. Iaitu, nombor sepadan dengan nilai pembilang kitaran. Nombor langkah dalam tatatanda perpuluhan biasa:

Akan ada sejumlah langkah n k. Dengan melalui nombor mereka dalam sistem nombor perpuluhan dan menukar setiap satu daripada mereka kepada sistem radix n, kami mendapat nilai indeks:

M:= bulat(IntPower(n, k)); untuk i:= 0 hingga M-1 mulakan Nombor:= i; untuk p:= 0 hingga k-1 mulakan Indeks := Nombor mod n; Bilangan:= Number div n; akhir; DoSomething(Indeks); akhir;

Mari kita perhatikan sekali lagi bahawa kaedah ini tidak universal dan anda perlu menghasilkan sesuatu yang berbeza untuk setiap tugas.

Soalan kawalan

1. Tentukan apa yang akan dilakukan oleh prosedur dan fungsi rekursif berikut.

(a) Apakah yang akan dicetak oleh prosedur berikut apabila Rec(4) dipanggil?

Prosedur Rec(a: integer); mula writeln(a); jika a>0 maka Rec(a-1); writeln(a); akhir;

(b) Apakah nilai bagi fungsi Nod(78, 26)?

Fungsi Nod(a, b: integer): integer; mulakan jika a > b kemudian Angguk:= Angguk(a – b, b) lain jika b > a maka Angguk:= Anggukan(a, b – a) yang lain Anggukan:= a; akhir;

Prosedur A(n: integer); prosedur B(n: integer); prosedur A(n: integer); mula writeln(n); B(n-1); akhir; prosedur B(n: integer); mula writeln(n); jika n

(d) Apakah yang akan dicetak oleh prosedur di bawah apabila memanggil BT(0, 1, 3)?

Prosedur BT(x: sebenar; D, MaxD: integer); mulakan jika D = MaxD kemudian tulisln(x) lain mulakan BT(x – 1, D + 1, MaxD); BT(x + 1, D + 1, MaxD); akhir; akhir;

2. Ouroboros - ular yang memakan ekornya sendiri (Rajah 14) apabila dibentangkan mempunyai panjang L, diameter di sekeliling kepala D, ketebalan dinding perut d. Tentukan berapa banyak ekor yang boleh dia picit ke dalam dirinya dan berapa banyak lapisan ekor itu akan diletakkan selepas itu?

nasi. 14. Ouroboros yang diperluaskan.

3. Bagi pokok dalam Rajah. 10a menunjukkan jujukan nod lawatan dalam susunan lintasan hadapan, belakang dan tamat.

4. Gambarkan secara grafik pokok yang ditakrifkan menggunakan kurungan bersarang: (A(B(C, D), E), F, G).

5. Gambarkan pepohon sintaks secara grafik untuk ungkapan aritmetik berikut:

Tulis ungkapan ini dalam tatatanda Poland terbalik.

6. Untuk graf di bawah (Rajah 15), tuliskan matriks bersebelahan dan matriks kejadian.

Tugasan

1. Setelah mengira faktorial dengan secukupnya sejumlah besar kali (sejuta atau lebih), bandingkan keberkesanan algoritma rekursif dan berulang. Berapakah perbezaan masa pelaksanaan dan bagaimanakah nisbah ini bergantung pada nombor yang pemfaktorannya dikira?

2. Tulis fungsi rekursif yang menyemak sama ada kurungan diletakkan dengan betul dalam rentetan. Pada penempatan yang betul syarat dipenuhi:

(a) bilangan kurungan pembuka dan penutup adalah sama.
(b) dalam mana-mana pasangan terdapat bukaan - kurungan penutup yang sepadan, kurungan diletakkan dengan betul.

Contoh peletakan yang salah:)(, ())(, ())((), dsb.

3. Garisan mungkin mengandungi kurungan bulat dan segi empat sama. Setiap kurungan pembukaan mempunyai kurungan penutup yang sepadan dengan jenis yang sama (bulat - bulat, segi empat sama). Tulis fungsi rekursif yang menyemak sama ada kurungan diletakkan dengan betul dalam kes ini.

Contoh peletakan yang salah: ([)].

4. Bilangan struktur kurungan sekata panjang 6 ialah 5: ()()(), (())(), ()(()), ((())), (()()).
Tulis atur cara rekursif untuk menjana semua struktur kurungan biasa dengan panjang 2 n.

Catatan: Struktur kurungan yang betul dengan panjang minimum "()". Struktur yang lebih panjang diperoleh daripada struktur yang lebih pendek dalam dua cara:

(a) jika struktur yang lebih kecil dimasukkan ke dalam kurungan,
(b) jika dua struktur yang lebih kecil ditulis secara berurutan.

5. Buat prosedur yang mencetak semua pilih atur yang mungkin untuk integer dari 1 hingga N.

6. Buat prosedur yang mencetak semua subset set (1, 2, ..., N).

7. Buat prosedur yang mencetak semua kemungkinan perwakilan nombor asli N sebagai hasil tambah nombor asli yang lain.

8. Cipta satu fungsi yang mengira jumlah unsur tatasusunan dengan kepada algoritma berikut: Tatasusunan dibahagikan kepada separuh, jumlah unsur dalam setiap separuh dikira dan ditambah. Jumlah unsur dalam separuh tatasusunan dikira menggunakan algoritma yang sama, iaitu sekali lagi dengan membahagi dua. Pembahagian berlaku sehingga kepingan tatasusunan yang terhasil mengandungi satu elemen setiap satu dan mengira jumlah, dengan itu, menjadi remeh.

Komen: Algoritma ini adalah alternatif. Dalam kes tatasusunan bernilai sebenar, ia biasanya membenarkan ralat pembundaran yang lebih kecil.

10. Buat prosedur yang melukis lengkung Koch (Rajah 12).

11. Hasilkan semula rajah itu. 16. Dalam rajah, pada setiap lelaran seterusnya bulatan adalah 2.5 kali lebih kecil (pekali ini boleh dijadikan parameter).

kesusasteraan

1. D. Knuth. Seni pengaturcaraan komputer. v. 1. (bahagian 2.3. “Pokok”).
2. N. Wirth. Algoritma dan struktur data.

Varg berkata:

Selamat tengah hari, saya benar-benar tidak dapat memahami cara fungsi ini melakukan pengiraan.

{
jika (n==1) kembalikan 1; //jika nilai baharu ialah 1, maka kami akan menambahnya dengan 1, dan bukan dengan yang sebelumnya. kerana yang sebelumnya adalah sifar. dan penambahan 1+0 akan menjadi tidak terhingga.
else kembalikan jumlah(n-1)+n; //tetapi jika n>1, kemudian tambahkannya dengan nilai sebelumnya sama dengan jumlah semua elemen hingga n
}

Mengikut pemahaman saya, dalam n ada 5, syarat tak padan baru puas hati kod ini sum(n-1)+n iaitu sesuatu yang diperoleh dalam kurungan dengan penolakan ditambah kepada 5, tetapi apakah (5 - 1)+5 dan jika ya, apakah yang menghentikan operasi aritmetik ini:?: :?: :?: Apakah nilai sebelumnya, dari mana ia datang, apakah ia bersamaan dengan:?: :?: :?:

Ya, hampir semuanya adalah seperti yang saya faham (dalam perenggan terakhir anda menunjukkan rekursi))), tetapi persoalannya tetap: bagaimana jumlah itu diperoleh, yang kemudiannya dipaparkan pada skrin?
Saya bekerja dengan Dev C++ untuk saya contoh ini memaparkan jumlah ==15, jika anda mengira seperti yang ditulis dalam contoh, maka jumlahnya ternyata berbeza.
Saya tulis di atas, mari ambil (5-1)+5=4+5=9

:
1+2+3+4+5 = 15. Contoh keluaran dengan betul.

(5) //Kami memberikan 5 kepada fungsi itu, menyemaknya untuk kesamaan dengan satu. tidak sama, memanggil fungsi semula, melepasi 5-1 ke dalamnya
(5-1+(5)) //...
(4-1+(5-1+(5)))
(3-1+(4-1+(5-1+(5))))
(2-1+(3-1+(4-1+(5-1+(5)))))

2-1 == 1, selesai memanggil fungsi.
(2-1+(3-1+(4-1+(5-1+(5))))) == 15
inilah hasilnya.
Di sini hasil fungsi ialah perbezaan dua nombor pertama, dan n ialah bahagian sebelah kanan yang lain
__________________________________
Anda hanya perlu memahami fungsi dengan betul dan menerimanya sebagai nilai yang dikira dan tidak memahaminya sebagai pembolehubah. Ia serupa dengan pembolehubah, tetapi lebih dekat dengan pemalar yang dikira, walaupun ia bukan pemalar, ia lebih mudah untuk melihatnya dengan cara ini.

Ya, ya, ya, saya tidak sempat menulis yang saya faham, semuanya betul, ada yang tidak berjaya dengan segera. Terima kasih tapak yang bagus))

Dan masih tidak logik sepenuhnya dalam baris ke-8 jika anda menukar nombor yang dikembalikan dari pulangan 1 kepada 2, jumlahnya berubah kepada 16. Bagaimanakah keadaan ini berkaitan dengan baris ke-9?
Dengan ini juga, semuanya jelas, hanya kembali 2 menambah kekurangannya kepada jumlah, boleh dikatakan.

:
bukan bintang tambahan, tetapi dua ini, dan jika anda menulis -3, maka apabila menambah sekali ia akan menolak tiga, dsb.
Keseluruhan logiknya ialah mana-mana fungsi rekursif memerlukan titik pulangan.
Sambungan dengan baris kesembilan ialah nombor dihantar ke fungsi jumlah apabila dipanggil dari dalam utama; semasa panggilan rekursif, nombor ini dikurangkan sebanyak satu (n-1) setiap kali, keputusan n-1 ini diperiksa untuk kesamaan dengan satu dan jika kesamaan adalah benar , maka keseluruhan jumlah yang diterima akan dijumlahkan dengan nombor dalam pulangan tersebut. jika tidak, keseluruhan jumlah akan dijumlahkan dengan n-1 baharu ini