If you're seeing this message, it means we're having trouble loading external resources on our website.

Jeżeli jesteś za filtrem sieci web, prosimy, upewnij się, że domeny *.kastatic.org i *.kasandbox.org są odblokowane.

Główna zawartość

Silnia rekurencyjna

Dla dodatnich wartości n, możemy zapisać n, !, jak już robiliśmy wcześniej, jako iloczyn liczb zaczynając od n i idąc w dół aż do 1: n, ! = n, dot, left parenthesis, n, minus, 1, right parenthesis, \@cdots, 2, dot, 1. Ale zauważ, że left parenthesis, n, minus, 1, right parenthesis, \@cdots, 2, dot, 1 to po prostu inny sposób zapisania left parenthesis, n, minus, 1, right parenthesis, !, więc możemy napisać, że n, !, equals, n, dot, left parenthesis, n, minus, 1, right parenthesis, !. Widziałeś, co przed chwilą zrobiliśmy? Napisaliśmy n, ! jako iloczyn, w którym jednym z czynników jest left parenthesis, n, minus, 1, right parenthesis, !. Powiedzieliśmy, że możesz obliczyć n, ! poprzez obliczenie left parenthesis, n, minus, 1, right parenthesis, ! a następnie pomnożenie wyniku otrzymanego z left parenthesis, n, minus, 1, right parenthesis, ! przez n. Możesz obliczyć silnię z n najpierw obliczając wartość silni z n, minus, 1. Powiedzieliśmy zatem, że obliczenie left parenthesis, n, minus, 1, right parenthesis, ! jest podproblemem który rozwiązujemy aby obliczyć n!
Spójrzmy na przykład: obliczyć 5!
  • Możesz obliczyć 5! jako 5, dot, 4, !.
  • Teraz musisz rozwiązać podproblem obliczenia 4!, który możesz policzyć jako 4, dot, 3!
  • Teraz musisz rozwiązać podproblem obliczenia 3!, które wynosi 3, dot, 2, !.
  • Teraz 2!, które jest równe 2, dot, 1, !.
  • Teraz musisz obliczyć 1!. Mógłbyś powiedzieć, że 1! jest równe 1, ponieważ jest to iloczyn wszystkich liczb całkowitych od 1 do 1. Lub możesz zastosować regułę, że 1, !, equals, 1, dot, 0, !. Zróbmy to przez zastosowanie formuły.
  • Zdefiniowaliśmy 0! jako równe 1.
  • Teraz możesz policzyć 1, !, equals, 1, dot, 0, !, equals, 1.
  • Mając obliczone 1, !, equals, 1, możesz policzyć 2, !, equals, 2, dot, 1, !, equals, 2.
  • Mając obliczone 2, !, equals, 2, możesz policzyć 3, !, equals, 3, dot, 2, !, equals, 6.
  • Mając obliczone 3, !, equals, 6, możesz policzyć 4, !, equals, 4, dot, 3, !, equals, 24.
  • W końcu, mając obliczone 4, !, equals, 24, możesz zakończyć przez obliczenie 5, !, equals, 5, dot, 4, !, equals, 120.
Poznaliśmy zatem inny sposób myślenia o tym jak można policzyć wartość n, !dla nieujemnych liczb całkowitych n:
  • Jeśli n, equals, 0, to z definicji n, !, equals, 1.
  • W przeciwnym przypadku n musi być dodatnie. Rozwiąż podproblem obliczenia left parenthesis, n, minus, 1, right parenthesis, !, pomnóż wynik przez n i ogłoś, że n, ! równa się wynikowi tego mnożenia.
Kiedy w ten sposób obliczamy 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.