Własności algorytmów rekurencyjnych

Podstawowa idea stojąca za algorytmami rekurencyjnymi:

Podczas obliczania $n!$‍, problem $n!$‍ (nasze zadanie), rozwiązujemy poprzez obliczenie silni mniejszej liczby, w tym przypadku $(n-1)!$‍ (mniejsza instancja problemu), a potem wykorzystujemy to rozwiązanie do obliczenia $n!$‍.

Aby rozwiązanie rekurencyjne działało, mniejsze pod-problemy muszą w końcu dotrzeć do przypadku bazowego. Przy obliczaniu $n!$‍, pod-problemy stają się coraz mniejsze, aż możemy obliczyć $0!$‍. Musisz mieć pewność, że w końcu trafisz na przypadek bazowy.

Na przykład, co jeśli staralibyśmy się obliczyć silnię liczby ujemnej naszą metodą rekursywną? Aby obliczyć $(-1)!$‍, najpierw spróbował byś obliczyć $(-2)!$‍, tak aby można by pomnożyć wynik przez $-1$‍. Ale do obliczenia $(-2)!$‍, trzeba obliczyć $(-3)!$‍, tak aby pomnożyć wynik przez $-2$‍. Potem trzeba obliczyć $(-3)!$‍ i tak dalej. Oczywiście, liczby stają się coraz mniejsze, ale również coraz dalej i dalej od przypadku bazowego $0!$‍. Nigdy nie otrzymasz odpowiedzi.

Nawet jeśli można zagwarantować, że wartość $n$‍ nie jest ujemna, możesz wpaść w kłopoty jeśli pod-problemy nie stają się stopniowo mniejsze. Oto przykład. Weźmy formułę $n!=n\cdot (n-1)!$‍ i podzielmy obie strony przez $n$‍, otrzymując $n!/n=(n-1)!$‍. Stwórzmy nową zmienną $m$‍ i oznaczmy ją jako $n+1$‍. Ponieważ nasz wzór ma zastosowanie dla liczb dodatnich, podstawmy $m$‍ za $n$‍, otrzymując $m!/m=(m-1)!$‍. Ponieważ $m=n+1$‍, obecnie mamy $(n+1)!/(n+1)=(n+1-1)!$‍. Zmieniając strony możemy stwierdzić $n+1-1=n$‍ daje nam $n!=(n+1)!/(n+1)$‍. Ten wzór prowadzi nas do przekonania, że możemy obliczyć $n!$‍ przez obliczenie $(n+1)!$‍, a potem podzielenie wyniku przez $n+1$‍. Ale do obliczenia $(n+1)!$‍, najpierw trzeba obliczyć $(n+2)!$‍, potem $(n+3)!$‍ i tak dalej. Nigdy nie dojdziemy od przypadku bazowego 0. Dlaczego nie? Bo każdy pod-problem rekursywnie prosi aby obliczyć wartość większą, a nie mniejszą. Jeśli $n$‍ jest dodatnie, nigdy nie przejdzie przypadek 0.

Możemy wydzielić dwa podstawowe zasady rekurencji:

Wróćmy do rosyjskich Matrioszek. Chociaż nie przedstawiają żadnych algorytmów, widać, że każda lalka obejmuję wszystkie mniejsze (analogicznie jak rekurencja), aż do najmniejszej lalki, która nie zawiera żadnej innej (jak przypadek bazowy).

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.