Grade 10 · RecursionCitește în română
Recursive factorial
Original: Factorial recursiv
The idea
The mathematical definition is already recursive: 0! = 1 and n! = n * (n - 1)!. The function has a stopping condition (n == 0) and a recursive call on a smaller problem (n - 1). The calls are pushed on the stack: fact(4) waits for fact(3), which waits for fact(2), and so on down to fact(0); the multiplications happen on the way back, in reverse order.
Original description (Romanian)
Definiția matematică este deja recursivă: 0! = 1 și n! = n * (n - 1)!. Funcția are o condiție de oprire (n == 0) și un autoapel pe o problemă mai mică (n - 1). Apelurile se pun pe stivă: fact(4) așteaptă fact(3), care așteaptă fact(2) și așa mai departe până la fact(0); la întoarcere se fac înmulțirile, în ordine inversă.
Examples
Input
5
Expected output
120
Input
0
Expected output
1
The code
Comments are in Romanian, as in the original collection. Edit freely: you can reset at any time.
/*
* Titlu: Factorial recursiv
* Clasa: 10
* Capitol: Recursivitate
* Descriere: Definiția matematică este deja recursivă: 0! = 1 și n! = n * (n - 1)!.
* Funcția are o condiție de oprire (n == 0) și un autoapel pe o problemă
* mai mică (n - 1). Apelurile se pun pe stivă: fact(4) așteaptă fact(3),
* care așteaptă fact(2) și așa mai departe până la fact(0); la întoarcere
* se fac înmulțirile, în ordine inversă.
* Complexitate: O(n) timp și O(n) memorie pe stivă
*
* Exemplu
* Intrare: 5
* Ieșire: 120
*
* Exemplu
* Intrare: 0
* Ieșire: 1
*/
#include <iostream>
using namespace std;
long long fact(int n)
{
if (n == 0)
return 1; // condiția de oprire
return n * fact(n - 1); // autoapel pe o problemă mai mică
}
int main()
{
int n;
cin >> n;
cout << fact(n) << '\n';
return 0;
}
Runs on a real g++ (C++17, -O2) through Compiler Explorer. Keep runs short; there's a time limit.