Rekursio

Rekursio

> LeekScript-opetusohjelma

Edellytykset:

• Pakollinen:
• Opi määrittelemään funktio.
• Suositus:
• Osaat käyttää anonyymejä toimintoja/sulkemisia.
• Hyödyllinen:
• Sinulla on käsitys siitä, mitkä ovat abstrakteja tietotyyppejä, erityisesti pino. cf: lähde
• Tiedä mitä [Memoisization] on (https://leekwars.com/encyclopedia/Optimisation#Pr%C3%A9parer_du_curry)

----

Rekursio on laajasti ottaen kohteen kykyä viitata itseensä. Todellisessa maailmassa tämä näkyy selvimmin fraktaaleissa, samoin kuin silloin, kun kaksi peiliä asetetaan vastakkain. Löydämme tämän käsitteen myös tyylin lauseista: "Näen unta, että näen unta, että näen unta." tai "Luulen kirjoittavani, että unelmoin että luulen kirjoittavani..." jne. Ohjelmoinnissa tämä ilmenee enimmäkseen funktioilla, jotka kutsuvat itseään:

function loop() { loop(); }

Yllä oleva funktio on yksinkertaisin rekursiivinen funktio. Kutsuttaessa se ei tee muuta kuin soittaa itseään. Tämä on sama kuin käyttäisit ääretöntä silmukkaa (esim. while(true);). Käytämme tätä funktiota perusrunkona kaikille tuleville rekursiivisille funktioillemme.

Rekursio

Rekursio on analoginen dekonstruktion kanssa. Se löytyy pääasiassa "Divide and Conquer" -tyyppisistä algoritmeista. Ongelmamme ratkaisemiseksi aloitamme jakamalla sen aliongelmiin, jotka on helpompi ratkaista, toistamme prosessia, kunnes löydämme ongelman, jonka tiedämme kuinka ratkaista suoraan, ja siitä lähtien ratkaisemme korkeammat ongelmat yhdistämällä aiemmat ongelmamme. ratkaisuja.

Aseta summa arvosta 0 arvoon n

Haluamme määrittää funktion, joka ottaa parametriksi kokonaisluvun n ja palauttaa 0:n summan arvoon n (esim. 0 + 1 + ... + n). Perusrungomme perusteella voimme aloittaa seuraavalla funktiolla:

funktio summaN(n) { summaN(?); palata?; }

Tällä hetkellä meillä on seuraavat tiedot:

• "n" tunnetaan;
• voimme kutsua sumN uudella arvolla;
• voimme käyttää uuden puhelun paluuta;
• "summaN" on palautettava numero;
• jossain on oltava lisäys;
• "silmukan" osalta "summaN" ei pysähdy. Meidän on keksittävä, kuinka se pysäytetään.

Rekursiivisesti työskennellessä on aina hyvä aloittaa pysähtymisehdolla. Rekursion tapauksessa haluamme lopettaa aliongelmien luomisen, kun olemme löytäneet jotain, jonka voimme ratkaista. Tässä tapauksessa summa "0" - "0" on jotain, jonka tiedämme kuinka ratkaista. "0" on siis perustapauksemme, voimme palauttaa vastaavan summan suoraan.

funktio summaN(n) { if (n === 0) { return 0; } else { summaN(?); palata?; } }

Meidän on nyt selvitettävä, kuinka päästään perustapaukseen. Voisimme vähentää "n" itsestään, mutta siinä tapauksessa emme pystyisi summaamaan kokonaislukuja "0" ja "n" välillä, meillä olisi vain "0" ja "n". Siksi meidän on luotava aliongelma, joka voi ratkaista summan, jonka n-luku on lähempänä perustapaustamme.

funktio summaN(n) { if (n === 0) { return 0; } else { summaN(n - 1); palata?; } }

Nyt tarvitsee tehdä vain summa, jota meiltä alussa kysyttiin. Tässä summa 0 - n on myös summa 0 - n - 1 ja n.

funktio summaN(n) { if (n === 0) { return 0; } else { paluu n + summaN(n - 1); } }

Kolmiosaisella:

funktio summaN(n) { palauttaa n === 0? 0 n + summaN(n - 1); }

Voit vapaasti kokeilla koodia Leekwars-editorissasi. Ehkä huomaat pääongelman rekursiossa. Voit myös visualisoida suorituksen (perustavalla) tällä sivustolla.

Corecursio

/!\ Uudelleen tehtävä osio, joka näytetään on enimmäkseen häntärekursio. Ei sovellu usealle haaralle. /!\ Korekursio on analoginen rakentamisen kanssa. Toisin kuin rekursiossa, jossa pyrimme pääsemään perustapaukseen pääongelmastamme, yhteisrekursiossa aloitamme suoraan perustapauksestamme ja siirrymme kohti pääongelman ratkaisua.

Keskinäinen rekursio

Olemme jo peittäneet keskinäisen rekursion peileillä ja lauseilla. Ohjelmoinnissa funktioiden kanssa tämä tarkoittaa sitä, että kaksi tai useampi funktio kutsuu toisiaan. Esittelemme alla yksinkertaisimman keskinäisen rekursion tapauksen:

function abuneLoop() { keskinäinenHelper(); }

toiminto mut