Silnia rekurencynie może być przestawiona na różne sposoby.
Poniżej podałem przykład przepisany z książki jak i moje dwie własne wersje które uważam za lepsze
#include <iostream>
int silnia_rek1(int n) {
if (n == 0)
return 1;
else
return n * silnia_rek1(n - 1);
}
int silnia_rek2(int n) {
if (n == 0)
return 1;
return n * silnia_rek1(n - 1);
}
- Wersja "jednolinijkowa" z użyciem operatora trójargumentowego
int silnia_rek(int n) {
return n == 0 ? 1 : n * silnia_rek(n - 1);
}
int main() {
std::cout << silnia_rek1(4) << std::endl;
std::cout << silnia_rek2(4) << std::endl;
std::cout << silnia_rek(4) << std::endl;
return 0;
}
Aby umieć rekurencyjnie rozwiązywać silnie musimy wiedzieć dwie rzeczy.
Najlepiej można to zrozumieć na wzorze rekurencyjnym silnii, który po prostu przenosimy na kod
[tex]silnia(n) = \left \{ {1} , \:dla \: n = 0\atop {n * silnia(n -1), \: dla \: n > 0 \left}}[/tex]
Czyli silnia z n = 0 wynosi 1, a silnia z każdej innej liczby to ta liczba * liczba o jeden mniejsza.
Dlatego jeśli liczymy rekurencyjnie silnie to liczymy ją "od końca" a gdy n będzie wynosić 0 zwracamy 1 i kończymy wywołania rekurencyjne tej silnii.
Np. silnia(3) = 3 * (3 - 1) * (2 - 1) * (1 - 1)
Zauważ, że takie obliczenie dałoby wynik 0, bo odejmowanie w ostatnim nawiasie daje 0, więc wynik całego iloczynu dawałby 0. Dlatego daliśmy warunek if(n == 0) return 1. Oznacza to, że jeśli nasze n miałoby wynosić 0, (czyli jak będzie 1 - 1) to nie zwróci 0, tylko 1 i zakończy się ciąg wywołań rekurencyjnych, co pozwoli przejść do obliczania wyniku naszej silnii czyli iloczynu 3 * 2 * 1 = 6
Dopóki jednak nasze n nie będzie wynosiło 0 będzie wynonywać się mnożenie naszej liczby przez liczbę o 1 mnieszą (czyli to co jest po else)
