Fibonacci and Factorial
In this page:
Factorial
The factorial of n (written n!) is the product of every positive integer up to n, and it's usually the very first example used to teach recursion because its recursive definition (n! = n times (n-1)!) mirrors the code almost exactly.
Example: Factorial
#include <iostream>
using namespace std;
int factorial(int n) {
if (n <= 1) return 1;
return n * factorial(n - 1);
}
int main() {
cout << factorial(5);
return 0;
}public class Main {
static int factorial(int n) {
if (n <= 1) return 1;
return n * factorial(n - 1);
}
public static void main(String[] args) {
System.out.println(factorial(5));
}
}def factorial(n):
if n <= 1:
return 1
return n * factorial(n - 1)
print(factorial(5))#include <stdio.h>
int factorial(int n) {
if (n <= 1) return 1;
return n * factorial(n - 1);
}
int main() {
printf("%d", factorial(5));
return 0;
}Login to try C/C++/Java code in the editor
Fibonacci
The Fibonacci sequence defines each number as the sum of the two before it (0, 1, 1, 2, 3, 5, 8...), making it a natural second recursion example since, unlike factorial, it needs two recursive calls per step instead of one.
Example: Fibonacci
#include <iostream>
using namespace std;
int fib(int n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}
int main() {
cout << fib(7);
return 0;
}public class Main {
static int fib(int n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}
public static void main(String[] args) {
System.out.println(fib(7));
}
}def fib(n):
if n <= 1:
return n
return fib(n - 1) + fib(n - 2)
print(fib(7))#include <stdio.h>
int fib(int n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}
int main() {
printf("%d", fib(7));
return 0;
}Login to try C/C++/Java code in the editor
Recursive Comparison
Factorial recursion is linear — each call makes exactly one further call, so the total work grows proportionally with n. Fibonacci's naive recursion branches into two calls at every step, so its total work grows exponentially even though the final numbers are simple.
Example: Recursive Comparison
#include <iostream>
using namespace std;
int calls = 0;
int fib(int n) {
calls++;
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}
int main() {
fib(10);
cout << "calls: " << calls;
return 0;
}public class Main {
static int calls = 0;
static int fib(int n) {
calls++;
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}
public static void main(String[] args) {
fib(10);
System.out.println("calls: " + calls);
}
}calls = 0
def fib(n):
global calls
calls += 1
if n <= 1:
return n
return fib(n - 1) + fib(n - 2)
fib(10)
print("calls:", calls)#include <stdio.h>
int calls = 0;
int fib(int n) {
calls++;
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}
int main() {
fib(10);
printf("calls: %d", calls);
return 0;
}Login to try C/C++/Java code in the editor
Memoization Idea
Because naive recursive Fibonacci recomputes the same smaller values over and over, storing already-computed results (memoization) avoids that repeated work and brings the running time down from exponential to linear.
Example: Memoization Idea
#include <iostream>
#include <unordered_map>
using namespace std;
unordered_map<int, int> memo;
int fib(int n) {
if (n <= 1) return n;
if (memo.count(n)) return memo[n];
return memo[n] = fib(n - 1) + fib(n - 2);
}
int main() {
cout << fib(30);
return 0;
}import java.util.*;
public class Main {
static HashMap<Integer, Integer> memo = new HashMap<>();
static int fib(int n) {
if (n <= 1) return n;
if (memo.containsKey(n)) return memo.get(n);
int result = fib(n - 1) + fib(n - 2);
memo.put(n, result);
return result;
}
public static void main(String[] args) {
System.out.println(fib(30));
}
}memo = {}
def fib(n):
if n <= 1:
return n
if n in memo:
return memo[n]
memo[n] = fib(n - 1) + fib(n - 2)
return memo[n]
print(fib(30))#include <stdio.h>
long memo[40] = {0};
long fib(int n) {
if (n <= 1) return n;
if (memo[n]) return memo[n];
return memo[n] = fib(n - 1) + fib(n - 2);
}
int main() {
printf("%ld", fib(30));
return 0;
}Login to try C/C++/Java code in the editor
Practice
Working through both problems by hand — tracing the call stack for factorial and drawing the branching call tree for Fibonacci — builds the intuition needed for harder recursive and dynamic programming problems later on.
Example: Practice
#include <iostream>
using namespace std;
int factorial(int n) { return n <= 1 ? 1 : n * factorial(n - 1); }
int fib(int n) { return n <= 1 ? n : fib(n - 1) + fib(n - 2); }
int main() {
cout << "5! = " << factorial(5) << ", fib(6) = " << fib(6);
return 0;
}public class Main {
static int factorial(int n) { return n <= 1 ? 1 : n * factorial(n - 1); }
static int fib(int n) { return n <= 1 ? n : fib(n - 1) + fib(n - 2); }
public static void main(String[] args) {
System.out.println("5! = " + factorial(5) + ", fib(6) = " + fib(6));
}
}def factorial(n):
return 1 if n <= 1 else n * factorial(n - 1)
def fib(n):
return n if n <= 1 else fib(n - 1) + fib(n - 2)
print("5! =", factorial(5), ", fib(6) =", fib(6))#include <stdio.h>
int factorial(int n) { return n <= 1 ? 1 : n * factorial(n - 1); }
int fib(int n) { return n <= 1 ? n : fib(n - 1) + fib(n - 2); }
int main() {
printf("5! = %d, fib(6) = %d", factorial(5), fib(6));
return 0;
}Login to try C/C++/Java code in the editor
Chapter Quiz — Complete all 7 topics to unlock
0/7 topics done
Complete these topics first: