Funkcija, kuri kviečia save

Nuo 3 pamokos žinai: funkcija gali kviesti kitą funkciją. O kas, jei funkcija pakviečia save?

Klasika — faktorialas: 4! = 4 × 3 × 2 × 1 = 24. Pastebėk savybę: 4! = 4 × 3! — didelė užduotis yra mažesnė tos pačios rūšies užduotis plius vienas žingsnis. Būtent tokioms užduotims rekursija ir tinka.

Kiekviena rekursinė funkcija turi DVI dalis:

• Bazinis atvejis — kada SUSTOTI: 1! = 1. Be jo kvietimai niekada nesibaigtų.
• Rekursinis atvejis — kaip SUMAŽINTI: n! = n × (n-1)!. Kiekvienas kvietimas privalo artėti prie bazinio.

Pasek ant popieriaus, kas vyksta kviečiant factorial(4):

factorial(4) → laukia 4 × factorial(3)
  factorial(3) → laukia 3 × factorial(2)
    factorial(2) → laukia 2 × factorial(1)
      factorial(1) → bazinis atvejis! grąžina 1
    factorial(2) = 2 × 1 = 2
  factorial(3) = 3 × 2 = 6
factorial(4) = 4 × 6 = 24

Kiekvienas kvietimas laukia vidinio atsakymo — jie kraunasi į kvietimų dėklą (call stack), o pasiekus bazinį atvejį dėklas išsivynioja atgal. Tas pats dėklas, kurio klaidą matei, kai programa lūžta — dabar žinai, kas jame gyvena.

Patarimas. Sąžiningai: tą patį factorial ciklas suskaičiuoja paprasčiau ir be dėklo augimo. Rekursija nugali ten, kur duomenys patys savyje panašūs — aplankas su aplankais, šeimos medis, žaidimo ėjimų medis. Tavo knygų lentyna — plokščias sąrašas, jai ciklo užtenka. Todėl ir sakom: paragaujam ir grįžtam prie ciklų.