Recursion from Scratch (2026)
Recursion is a fundamental programming technique where a function calls itself to solve smaller instances of the same problem. Every recursive solution has a base case (which stops the recursion) and a recursive case (which reduces the problem toward the base case). Recursion is natural for problems involving trees, graphs, divide and conquer, backtracking, and mathematical sequences.
In this tutorial, we will understand the recursion tree, explore tail recursion and its optimization, implement classic examples like factorial and Fibonacci, and learn to convert between recursive and iterative solutions.
Base Case and Recursive Case
Every recursive function must have at least one base case to prevent infinite recursion. The base case returns a value without making any further recursive calls. The recursive case breaks the problem into smaller subproblems, makes recursive calls, and combines the results. Without a proper base case, recursion leads to stack overflow.
The base case is like the stopping condition in a loop. For factorial, the base case is n <= 1 returning 1. For Fibonacci, the base cases are fib(0) = 0 and fib(1) = 1.
factorial = lambda n: 1 if n <= 1 else n * factorial(n - 1)
def fibonacci(n):
if n <= 0: return 0
if n == 1: return 1
return fibonacci(n - 1) + fibonacci(n - 2)
power = lambda base, exp: 1 if exp == 0 else base * power(base, exp - 1)
def sum_digits(n):
if n < 10: return n
return n % 10 + sum_digits(n // 10)
def reverse_string(s):
if len(s) <= 1: return s
return reverse_string(s[1:]) + s[0]
print(factorial(5)) # 120
print(fibonacci(10)) # 55
print(power(2, 10)) # 1024
print(sum_digits(12345)) # 15Recursion Tree and Call Stack
When a recursive function is called, each call adds a new frame to the call stack. The recursion tree visualizes all the function calls as a tree structure, where each node represents a function call and its children are the recursive calls it makes. Understanding the recursion tree helps in analyzing time complexity and identifying redundant computations.
For Fibonacci, the recursion tree has exponential nodes (2^n) because the same subproblems are computed repeatedly. This insight leads to dynamic programming optimization. The space complexity of recursion is O(depth) for the call stack.
#include
#include Tail Recursion
A tail-recursive function makes the recursive call as the last operation, with no computation after it. Some compilers and interpreters optimize tail recursion into a loop, preventing stack overflow. This optimization is called Tail Call Optimization (TCO). In languages like Scheme and Scala, TCO is guaranteed. In Python, it is not guaranteed but can be manually optimized.
Tail recursion converts the implicit stack of recursion into explicit accumulator parameters. For example, factorial with an accumulator: fact(n, acc=1) calls fact(n-1, n*acc) instead of n * fact(n-1).
public class TailRecursion {
static long factorial(int n, long acc) {
if (n <= 1) return acc;
return factorial(n - 1, n * acc);
}
static int sum(int n, int acc) {
if (n == 0) return acc;
return sum(n - 1, acc + n);
}
static long power(long base, int exp, long acc) {
if (exp == 0) return acc;
return power(base, exp - 1, acc * base);
}
static long factorialIterative(int n) {
long acc = 1;
while (n > 1) { acc *= n; n--; }
return acc;
}
public static void main(String[] args) {
System.out.println(factorial(10, 1));
System.out.println(sum(100, 0));
}
}Recursion Best Practices
Key best practices for recursion: always define a clear base case, ensure each recursive call makes progress toward the base case, and consider the stack depth for large inputs. Use memoization to avoid redundant computations in overlapping subproblems. Convert to iteration when stack depth is a concern.
Recursion is ideal for tree traversal, graph DFS, divide and conquer algorithms, backtracking, and parsing nested structures. For simple linear recursion (like factorial), iteration is often preferred for efficiency.
import functools
@functools.lru_cache(maxsize=None)
def fibonacci_optimized(n):
if n <= 0: return 0
if n == 1: return 1
return fibonacci_optimized(n - 1) + fibonacci_optimized(n - 2)
def sum_iterative(n):
result = 0
while n > 0: result += n; n -= 1
return result
class TreeNode:
def __init__(self, val, left=None, right=None):
self.val = val; self.left = left; self.right = right
def inorder_traversal(node):
if node is None: return []
return inorder_traversal(node.left) + [node.val] + inorder_traversal(node.right)
def tree_height(node):
if node is None: return 0
return 1 + max(tree_height(node.left), tree_height(node.right))Frequently Asked Questions
When to use recursion vs iteration?
Use recursion for tree/graph traversal, divide and conquer, backtracking, and nested structures. Use iteration for simple loops, when stack depth is a concern, or when performance is critical.
What is tail recursion?
Tail recursion is when the recursive call is the last operation. Some compilers optimize it into a loop (TCO). It prevents stack overflow and is equivalent to iteration.
How to avoid stack overflow in recursion?
Use tail recursion or convert to iteration. Limit recursion depth. Use memoization to avoid redundant calls. For deep recursion, consider an explicit stack data structure.
What is the recursion tree?
The recursion tree visualizes all function calls as a tree. Each node is a call, children are recursive calls. It helps analyze time complexity and identify redundant computations.
Originally published on Ayodhyyya. Last updated June 1, 2026.