Rekurencja

Czy widziałeś kiedyś Matrioszkę - zestaw rosyjskich laleczek? Na początku widzisz tylko jedną figurkę, zwykle pomalowane drewno, które wygląda tak:

Możesz zdjąć górna połowę pierwszej figurki i co zobaczysz w środku? Kolejną, nieco mniejszą rosyjską lalkę!

Możesz wyjąć tę lalkę i rozdzielić górna połowę od dolnej. Wtedy zobaczysz kolejną jeszcze mniejszą Matrioszkę:

I jeszcze raz:

I możesz tak kontynuować i rozdzielać kolejne figurki. Ostatecznie znajdziesz maleńką rosyjską laleczkę, zbudowaną z jednego kawałka drewna, w związku z tym, ostatnia już się nie otwiera:

Rozpoczęliśmy od jednej dużej rosyjskiej lalki, a potem znajdowaliśmy coraz to mniejsze laleczki, dopóki nie zobaczyliśmy tak małej, że nie mogła ona już w środku pomieścić następnej.

Co ma wspólnego Matrioszka z algorytmami? Tak jak rosyjska lalka ma w sobie mniejszą lalkę, a ta posiada jeszcze mniejszą i tak dalej aż trafimy na laleczkę, która jest zbyt mała, aby pomieścić następną, tak my zobaczymy jak zaprojektować algorytm, który rozwiąże problem, rozwiązując najpierw mniejszy przypadek tego samego problemu, dopóki ten problem nie jest tak mały, aby rozwiązać go bezpośrednio. Taką technikę nazywamy rekurencją.

Rekurencję posiada wiele zastosowań. W tym module, dowiemy się jak korzystać z rekurencji, aby wyliczyć silnię, ustalić czy dane słowo jest palindromem, obliczyć potęgę liczby, narysować fraktal, i rozwiązać starożytny problem Wież Hanoi. Następne moduły będą używać rekurencji do rozwiązywania innych problemów, włączając sortowanie.

Materiał powstał we współpracy profesorów z Dartmouth Computer Science Thomasa Cormena i Devina Balkcoma oraz zespołu nauczycieli informatyki Khan Academy. Materiał jest udostępniony na licencji CC-BY-NC-SA.