Silnia rekurencyjna

Dla dodatnich wartości $n$n, możemy zapisać $n!$n, !, jak już robiliśmy wcześniej, jako iloczyn liczb zaczynając od $n$n i idąc w dół aż do 1: $n!$n, ! = $n \cdot (n-1) \cdots 2 \cdot 1$n, dot, left parenthesis, n, minus, 1, right parenthesis, \@cdots, 2, dot, 1. Ale zauważ, że $(n-1) \cdots 2 \cdot 1$left parenthesis, n, minus, 1, right parenthesis, \@cdots, 2, dot, 1 to po prostu inny sposób zapisania $(n-1)!$left parenthesis, n, minus, 1, right parenthesis, !, więc możemy napisać, że $n! = n \cdot (n-1)!$n, !, equals, n, dot, left parenthesis, n, minus, 1, right parenthesis, !. Widziałeś, co przed chwilą zrobiliśmy? Napisaliśmy $n!$n, ! jako iloczyn, w którym jednym z czynników jest $(n-1)!$left parenthesis, n, minus, 1, right parenthesis, !. Powiedzieliśmy, że możesz obliczyć $n!$n, ! poprzez obliczenie $(n-1)!$left parenthesis, n, minus, 1, right parenthesis, ! a następnie pomnożenie wyniku otrzymanego z $(n-1)!$left parenthesis, n, minus, 1, right parenthesis, ! przez $n$n. Możesz obliczyć silnię z $n$n najpierw obliczając wartość silni z $n-1$n, minus, 1. Powiedzieliśmy zatem, że obliczenie $(n-1)!$left parenthesis, n, minus, 1, right parenthesis, ! jest podproblemem który rozwiązujemy aby obliczyć $n$n!

Spójrzmy na przykład: obliczyć 5!

Poznaliśmy zatem inny sposób myślenia o tym jak można policzyć wartość $n!$n, !dla nieujemnych liczb całkowitych $n$n:

Kiedy w ten sposób obliczamy $n!$n, !, odwołujemy się do pierwszego przypadku, w którym natychmiast znamy odpowiedź, czyli przypadku bazowego, a następnie wywołujemy drugi przypadek, w którym liczymy tą samą funkcję, ale przy użyciu innych wartości, czyli przypadek rekurencyjny.

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.