Główna zawartość
Informatyka
Kurs: Informatyka > Rozdział 1
Lekcja 6: Algorytmy rekurencyjne- Rekurencja
- Funkcja silnia
- Wyzwanie: silnia iterowana
- Silnia rekurencyjna
- Wyzwanie: silnia rekurencyjna
- Własności algorytmów rekurencyjnych
- Wykorzystanie rekurencji do zbadania czy słowo jest palindromem
- Wyzwanie: czy ten ciąg znaków to palindrom?
- Obliczanie potęgi danej liczby
- Wyzwanie: Potęgi rekurencyjne
- Wielokrotna rekurencja na przykładzie Trójkąta Sierpińskiego
- Ulepszanie wydajności funkcji rekurencyjnych
- Projekt: Sztuka rekurencji
© 2023 Khan AcademyWarunki użytkowaniapolitykę prywatnościInformacja o plikach cookie
Silnia rekurencyjna
Dla dodatnich wartości , możemy zapisać , jak już robiliśmy wcześniej, jako iloczyn liczb zaczynając od i idąc w dół aż do 1: = . Ale zauważ, że to po prostu inny sposób zapisania , więc możemy napisać, że . Widziałeś, co przed chwilą zrobiliśmy? Napisaliśmy jako iloczyn, w którym jednym z czynników jest . Powiedzieliśmy, że możesz obliczyć poprzez obliczenie a następnie pomnożenie wyniku otrzymanego z przez . Możesz obliczyć silnię z najpierw obliczając wartość silni z . Powiedzieliśmy zatem, że obliczenie jest podproblemem który rozwiązujemy aby obliczyć !
Spójrzmy na przykład: obliczyć 5!
- Możesz obliczyć 5! jako
. - Teraz musisz rozwiązać podproblem obliczenia 4!, który możesz policzyć jako
! - Teraz musisz rozwiązać podproblem obliczenia 3!, które wynosi
. - Teraz 2!, które jest równe
. - 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
. Zróbmy to przez zastosowanie formuły. - Zdefiniowaliśmy 0! jako równe 1.
- Teraz możesz policzyć
. - Mając obliczone
, możesz policzyć . - Mając obliczone
, możesz policzyć . - Mając obliczone
, możesz policzyć . - W końcu, mając obliczone
, możesz zakończyć przez obliczenie .
Poznaliśmy zatem inny sposób myślenia o tym jak można policzyć wartość dla nieujemnych liczb całkowitych :
- Jeśli
, to z definicji . - W przeciwnym przypadku
musi być dodatnie. Rozwiąż podproblem obliczenia , pomnóż wynik przez i ogłoś, że równa się wynikowi tego mnożenia.
Kiedy w ten sposób obliczamy , 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.
Chcesz dołączyć do dyskusji?
Na razie brak głosów w dyskusji