Recursion is a technique where a function calls itself to solve a smaller version of the same problem. Every recursive solution has two essential parts:
Each recursive call is pushed onto the call stack. When the base case is reached, the stack unwinds and results are returned back up the chain.
| Aspect | Recursion | Iteration |
|---|---|---|
| Code clarity | Often cleaner for tree/graph problems | Cleaner for simple loops |
| Memory | O(n) stack space per call depth | O(1) typically |
| Speed | Slower (function call overhead) | Faster |
| Stack overflow risk | Yes - deep recursion can overflow | No |
| Best for | Trees, graphs, divide & conquer, backtracking | Simple loops, performance-critical code |
Tail recursion is when the recursive call is the last operation in the function. Some compilers/runtimes optimize tail calls to avoid growing the stack (tail call optimization - TCO). Python does NOT support TCO; C++ and Java compilers may optimize it.
#include <iostream>
#include <unordered_map>
using namespace std;
// Factorial - O(n) time, O(n) space (call stack)
long long factorial(int n) {
if (n <= 1) return 1; // base case
return n * factorial(n - 1); // recursive case
}
// Fibonacci naive - O(2^n) time - very slow!
int fibNaive(int n) {
if (n <= 1) return n;
return fibNaive(n - 1) + fibNaive(n - 2);
}
// Fibonacci memoized - O(n) time, O(n) space
unordered_map<int, long long> memo;
long long fibMemo(int n) {
if (n <= 1) return n;
if (memo.count(n)) return memo[n];
memo[n] = fibMemo(n - 1) + fibMemo(n - 2);
return memo[n];
}
int main() {
cout << "5! = " << factorial(5) << endl; // 120
cout << "10! = " << factorial(10) << endl; // 3628800
cout << "fib(10) naive = " << fibNaive(10) << endl; // 55
cout << "fib(40) memo = " << fibMemo(40) << endl; // 102334155
return 0;
}import java.util.HashMap;
import java.util.Map;
public class Recursion {
// Factorial - O(n) time, O(n) space
static long factorial(int n) {
if (n <= 1) return 1;
return n * factorial(n - 1);
}
// Fibonacci naive - O(2^n) time
static int fibNaive(int n) {
if (n <= 1) return n;
return fibNaive(n - 1) + fibNaive(n - 2);
}
// Fibonacci memoized - O(n) time
static Map<Integer, Long> memo = new HashMap<>();
static long fibMemo(int n) {
if (n <= 1) return n;
if (memo.containsKey(n)) return memo.get(n);
long result = fibMemo(n - 1) + fibMemo(n - 2);
memo.put(n, result);
return result;
}
public static void main(String[] args) {
System.out.println("5! = " + factorial(5)); // 120
System.out.println("10! = " + factorial(10)); // 3628800
System.out.println("fib(10) = " + fibNaive(10)); // 55
System.out.println("fib(40) = " + fibMemo(40)); // 102334155
}
}from functools import lru_cache
# Factorial - O(n) time, O(n) space
def factorial(n):
if n <= 1: return 1 # base case
return n * factorial(n - 1) # recursive case
# Fibonacci naive - O(2^n) time - very slow!
def fib_naive(n):
if n <= 1: return n
return fib_naive(n - 1) + fib_naive(n - 2)
# Fibonacci memoized with dict - O(n) time
def fib_memo(n, memo={}):
if n <= 1: return n
if n in memo: return memo[n]
memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
return memo[n]
# Fibonacci with @lru_cache decorator - cleanest approach
@lru_cache(maxsize=None)
def fib(n):
if n <= 1: return n
return fib(n - 1) + fib(n - 2)
print(f"5! = {factorial(5)}") # 120
print(f"10! = {factorial(10)}") # 3628800
print(f"fib(10) = {fib_naive(10)}") # 55
print(f"fib(40) = {fib(40)}") # 102334155// Factorial - O(n) time, O(n) space
function factorial(n) {
if (n <= 1) return 1; // base case
return n * factorial(n - 1); // recursive case
}
// Fibonacci naive - O(2^n) time
function fibNaive(n) {
if (n <= 1) return n;
return fibNaive(n - 1) + fibNaive(n - 2);
}
// Fibonacci memoized - O(n) time
function fibMemo(n, memo = new Map()) {
if (n <= 1) return n;
if (memo.has(n)) return memo.get(n);
const result = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
memo.set(n, result);
return result;
}
console.log("5! =", factorial(5)); // 120
console.log("10! =", factorial(10)); // 3628800
console.log("fib(10) =", fibNaive(10)); // 55
console.log("fib(40) =", fibMemo(40)); // 102334155Tower of Hanoi is a classic recursion problem: move n disks from source peg to destination peg using an auxiliary peg, never placing a larger disk on a smaller one. It requires 2^n - 1 moves - O(2^n) time.
#include <iostream>
using namespace std;
// Tower of Hanoi - O(2^n) moves
void hanoi(int n, char from, char to, char aux) {
if (n == 1) {
cout << "Move disk 1 from " << from << " to " << to << endl;
return;
}
hanoi(n - 1, from, aux, to); // move n-1 disks to aux
cout << "Move disk " << n << " from " << from << " to " << to << endl;
hanoi(n - 1, aux, to, from); // move n-1 disks from aux to dest
}
int main() {
int n = 3;
cout << "Tower of Hanoi with " << n << " disks:" << endl;
hanoi(n, 'A', 'C', 'B');
// Total moves = 2^n - 1 = 7
return 0;
}public class TowerOfHanoi {
static void hanoi(int n, char from, char to, char aux) {
if (n == 1) {
System.out.println("Move disk 1 from " + from + " to " + to);
return;
}
hanoi(n - 1, from, aux, to);
System.out.println("Move disk " + n + " from " + from + " to " + to);
hanoi(n - 1, aux, to, from);
}
public static void main(String[] args) {
int n = 3;
System.out.println("Tower of Hanoi with " + n + " disks:");
hanoi(n, 'A', 'C', 'B');
// Total moves = 2^n - 1 = 7
}
}def hanoi(n, from_peg, to_peg, aux_peg):
if n == 1:
print(f"Move disk 1 from {from_peg} to {to_peg}")
return
hanoi(n - 1, from_peg, aux_peg, to_peg) # move n-1 to aux
print(f"Move disk {n} from {from_peg} to {to_peg}")
hanoi(n - 1, aux_peg, to_peg, from_peg) # move n-1 from aux to dest
n = 3
print(f"Tower of Hanoi with {n} disks:")
hanoi(n, 'A', 'C', 'B')
# Total moves = 2^n - 1 = 7function hanoi(n, from, to, aux) {
if (n === 1) {
console.log(`Move disk 1 from ${from} to ${to}`);
return;
}
hanoi(n - 1, from, aux, to); // move n-1 to aux
console.log(`Move disk ${n} from ${from} to ${to}`);
hanoi(n - 1, aux, to, from); // move n-1 from aux to dest
}
const n = 3;
console.log(`Tower of Hanoi with ${n} disks:`);
hanoi(n, 'A', 'C', 'B');
// Total moves = 2^n - 1 = 7Explore 500+ free tutorials across 20+ languages and frameworks.