What Is Recursion? A Simple Explanation With Code Examples in Python, JavaScript and Java

Recursion trips up most beginners because the function seems to use itself before it is finished. The trick is to stop tracing every call and trust one idea: if the function works for a smaller input, you can use that answer to solve the bigger one.

Recursion in one picture

Think of Russian nesting dolls. To find the smallest doll you open the current one: if it is solid you are done (the base case), otherwise you open the doll inside it and repeat (the recursive case). The task stays the same at every size; only the doll gets smaller.

In code the same shape looks like this. factorial(5) means 5 x 4 x 3 x 2 x 1, and each call hands a smaller factorial to the next:

def factorial(n):
    if n == 0 or n == 1:      # base case
        return 1
    return n * factorial(n - 1)   # recursive case: a smaller problem

print(factorial(5))

Output: 120

The two parts every recursive function needs

• Base case. The smallest input you can answer without calling yourself, such as an empty list or n = 0. It stops the recursion.
• Recursive case. The part that calls the function again on a smaller or simpler input, then uses the result.
• Progress. Each call must move closer to the base case. If the input never shrinks, the base case is never reached.

How the call stack runs factorial(4)

Each call waits on the call below it. The calls pile up on the call stack until the base case returns, then the answers unwind back up:

The deepest call (factorial(1)) returns first. That is why a missing base case ends in a stack overflow: the pile of waiting calls never stops growing.

Five recursion examples

1. Sum of a list (Python)

def total(numbers):
    if not numbers:                 # base case: nothing left to add
        return 0
    return numbers[0] + total(numbers[1:])

print(total([1, 2, 3, 4]))

Output: 10

2. Reverse a string (Python)

def reverse(text):
    if len(text) <= 1:              # base case
        return text
    return reverse(text[1:]) + text[0]

print(reverse("masai"))

Output: iasam

3. Flatten a nested list (Python)

Recursion fits nested data naturally, because a nested list is a list made of smaller lists.

def flatten(items):
    result = []
    for item in items:
        if isinstance(item, list):
            result.extend(flatten(item))   # recurse into the nested list
        else:
            result.append(item)
    return result

print(flatten([1, [2, [3, 4]], 5]))

Output: [1, 2, 3, 4, 5]

4. Fibonacci, slow and fast (JavaScript)

The plain version calls itself twice per step and repeats work. Storing results in a Map (memoization) fixes it.

function fib(n) {
  if (n <= 1) return n;            // base cases: fib(0) = 0, fib(1) = 1
  return fib(n - 1) + fib(n - 2);
}

const memo = new Map();
function fibFast(n) {
  if (n <= 1) return n;
  if (memo.has(n)) return memo.get(n);
  const value = fibFast(n - 1) + fibFast(n - 2);
  memo.set(n, value);
  return value;
}

console.log(fib(10), fibFast(50));

Output: 55 12586269025

5. Fast power (JavaScript)

Halving the exponent each call makes this take about log n steps instead of n.

function power(base, exponent) {
  if (exponent === 0) return 1;                 // base case
  const half = power(base, Math.floor(exponent / 2));
  return exponent % 2 === 0 ? half * half : half * half * base;
}

console.log(power(2, 10), power(3, 5));

Output: 1024 243

Bonus: Tower of Hanoi (Python)

Moving n discs needs 2^n - 1 moves, so 3 discs need 7.

def hanoi(n, source, target, spare, moves):
    if n == 0:
        return
    hanoi(n - 1, source, spare, target, moves)
    moves.append(f"{source}->{target}")
    hanoi(n - 1, spare, target, source, moves)

moves = []
hanoi(3, "A", "C", "B", moves)
print(len(moves), moves)

Output: 7 ['A->C', 'A->B', 'C->B', 'A->C', 'B->A', 'B->C', 'A->C']

The same idea in Java

public class Recursion {
    static long factorial(int n) {
        if (n <= 1) return 1;            // base case
        return n * factorial(n - 1);     // recursive case
    }

    public static void main(String[] args) {
        System.out.println(factorial(5));   // 120
    }
}

Recursion vs iteration

Anything recursive can be written with a loop and an explicit stack, and the reverse is also true. Choose recursion when the problem is naturally self-similar, and a loop when it is just repetition.

Python limits recursion depth, which you can see here:

import sys

def count_down(n):
    if n == 0:
        return 0
    return count_down(n - 1)

print(sys.getrecursionlimit())
try:
    count_down(5000)
except RecursionError:
    print("RecursionError: maximum recursion depth exceeded")

Output: 1000 then the RecursionError message. Python and Java do not optimise tail calls, so very deep recursion should become a loop. In Java the equivalent failure is a StackOverflowError.

Time and space complexity of common recursions

How to think recursively in four steps

1. Say in one sentence what the function returns for any input, for example: returns the sum of every number in the list.
2. Write the smallest case you can answer directly. That is the base case.
3. Assume the function already works for a smaller input.
4. Use that answer to build the answer for the current input.

This is the same logic as mathematical induction. If you can prove the base case and show that n follows from n - 1, the whole chain is correct.

Common mistakes

• No base case, or one that is never reached. The program ends in a stack overflow.
• The input does not shrink. Calling f(n) from f(n) is an infinite loop.
• Forgetting to return the recursive result. The call runs but the answer is lost.
• Repeating work. Overlapping calls, as in plain Fibonacci, need memoization or dynamic programming.
• Copying large lists in every call. Slicing in Python costs O(n) each time; pass an index instead when speed matters.

Where recursion is used in real software

• Walking a folder tree, where every folder can contain more folders.
• Parsing nested JSON, HTML or expressions.
• Tree and graph traversal, including depth-first search.
• Divide-and-conquer sorting, such as merge sort and quicksort.
• Backtracking: solving sudoku, N-Queens and generating permutations.

Practice problems, in order

1. Fibonacci Number (warm-up)
2. Climbing Stairs (recursion, then memoization)
3. Pow(x, n) (divide and conquer)
4. Maximum Depth of Binary Tree (recursion on trees)
5. Reverse Linked List (recursive version)
6. Generate Parentheses (backtracking)
7. Subsets and Permutations (backtracking)

Trace the first few by hand on paper, or watch the stack in Python Tutor. For a longer walk-through, read the Masai guide on how recursion works and recursion vs iteration.

Frequently asked questions

Learn this with mentors

Programmes for builders and engineers with admissions open: live classes, mentors and project work.

Leap AI Residency CohortMasai

8 weeks→

Advanced Certification in AI & MLVishlesan i-Hub, IIT Patna

8 months→

AI & ML Certification ProgramE&ICT Academy, IIT Roorkee

6 months→