Recursion is a function solving a problem by calling itself on a smaller version of the same problem. It is the natural shape of divide and conquer, tree and graph traversal, backtracking and dynamic programming — and the source of the classic bugs: a missing base case and a blown call stack.

Kind	Shape	Example
Direct recursion	`f` calls `f`	`fact(n)` calls `fact(n − 1)`
Indirect (mutual) recursion	`f` calls `g`, `g` calls `f`	`is_even(n)` calls `is_odd(n − 1)`, which calls `is_even(n − 2)`
Not recursion	a loop repeats a block without a new call	`for i in range(n): print("GFG")` — the original notes' first example is this, a plain loop

Recursion background: how calls nest

A function call does not finish until the function it called has returned. The program below shows the order in which lines run when fun2 calls fun1: the before lines go in, the after lines come out in reverse. Recursion is exactly this picture with the same function on every level.

Python

def fun1():
    print("Function 1 is called")

def fun2():
    print("Before Function 1")
    fun1()                       # fun2 pauses here until fun1 returns
    print("After Function 1")

print("Before Function 2")
fun2()
print("After Function 2")

C++

#include <iostream>
using namespace std;

void fun1() {
    cout << "Function 1 is called\n";
}

void fun2() {
    cout << "Before Function 1\n";
    fun1();                      // fun2 pauses here until fun1 returns
    cout << "After Function 1\n";
}

int main() {
    cout << "Before Function 2\n";
    fun2();
    cout << "After Function 2\n";
}

Java

public class Main {
    static void fun1() {
        System.out.println("Function 1 is called");
    }

    static void fun2() {
        System.out.println("Before Function 1");
        fun1();                  // fun2 pauses here until fun1 returns
        System.out.println("After Function 1");
    }

    public static void main(String[] args) {
        System.out.println("Before Function 2");
        fun2();
        System.out.println("After Function 2");
    }
}

JavaScript

function fun1() {
    console.log("Function 1 is called");
}

function fun2() {
    console.log("Before Function 1");
    fun1();                      // fun2 pauses here until fun1 returns
    console.log("After Function 1");
}

console.log("Before Function 2");
fun2();
console.log("After Function 2");

Output

Before Function 2
Before Function 1
Function 1 is called
After Function 1
After Function 2

Every active call lives in a frame on the call stack holding its parameters, local variables and the point to return to. A recursive function has one frame per pending call, so fact(3) builds three frames before the first multiplication happens:

The call stack while computing fact(3)

fact(3)                      call stack (top = running)        returns
  └─ 3 * fact(2)             ┌──────────┐
       └─ 2 * fact(1)        │ fact(0)  │  → 1                 1
            └─ 1 * fact(0)   │ fact(1)  │  → 1 * 1             1
                 └─ 1        │ fact(2)  │  → 2 * 1             2
                             │ fact(3)  │  → 3 * 2             6
                             └──────────┘
frames are pushed going down (3, 2, 1, 0) and popped coming back up (0, 1, 2, 3)

Typical structure of a recursive function

Every correct recursive function has the same two parts. Get either one wrong and the function never terminates — that is a stack overflow, not an infinite loop, because each call allocates a frame until memory runs out.

Base case(s) first
The smallest input, answered directly: if n == 0: return 1. There can be several (n == 0 or n == 1 for Fibonacci).
Recursive case
Call the function on a strictly smaller input (n − 1, n // 2, a shorter string, a subtree) and combine the result with the current level's work.
Convince yourself it ends
Each call must move towards a base case: n − 1 reaches 0; n // 2 reaches 0; start + 1 reaches end. A call with the same parameters is an infinite recursion.

Template of a recursive function

def fun(parameters):
    if base case:                 # answer directly, no call
        return simple answer
    # at least one parameter changes so the call moves towards the base case
    return combine(current work, fun(smaller parameters))

Where recursion is used

Factorial and Fibonacci: two shapes of recursion

Factorial makes one recursive call per level: n calls in total, O(n) time. Fibonacci as written in the definition makes two: fib(n−1) and fib(n−2) each recompute the same values again and again, so the number of calls grows like 2 · fib(n+1) − 1 — exponential. The program counts the calls to make this visible.

The call tree of naive fib(5): 15 calls for an answer of 5

                        fib(5)
                   /             \
              fib(4)              fib(3)
             /      \            /      \
         fib(3)    fib(2)    fib(2)    fib(1)
        /     \    /    \    /    \
    fib(2) fib(1) fib(1) fib(0) fib(1) fib(0)
    /    \
fib(1) fib(0)                 fib(3) is computed twice, fib(2) three times

Python

calls = 0

def fact(n):                  # one call per level: O(n)
    global calls
    calls += 1
    if n == 0:                # base case: 0! = 1
        return 1
    return n * fact(n - 1)

def fib(n):                   # two calls per level: O(2^n) — the same values recomputed
    global calls
    calls += 1
    if n == 0 or n == 1:      # two base cases: fib(0) = 0, fib(1) = 1
        return n
    return fib(n - 1) + fib(n - 2)

for n in (5, 10):
    calls = 0
    print(f"fact({n}) = {fact(n)} in {calls} calls")
for n in (5, 10, 20):
    calls = 0
    print(f"fib({n}) = {fib(n)} in {calls} calls")

C++

#include <iostream>
using namespace std;

long long calls = 0;

long long fact(int n) {           // one call per level: O(n)
    calls++;
    if (n == 0) return 1;         // base case: 0! = 1
    return n * fact(n - 1);
}

long long fib(int n) {            // two calls per level: O(2^n) — the same values recomputed
    calls++;
    if (n == 0 || n == 1) return n;   // two base cases
    return fib(n - 1) + fib(n - 2);
}

int main() {
    for (int n : {5, 10}) {
        calls = 0;
        long long r = fact(n);
        cout << "fact(" << n << ") = " << r << " in " << calls << " calls\n";
    }
    for (int n : {5, 10, 20}) {
        calls = 0;
        long long r = fib(n);
        cout << "fib(" << n << ") = " << r << " in " << calls << " calls\n";
    }
}

Java

public class Main {
    static long calls = 0;

    static long fact(int n) {             // one call per level: O(n)
        calls++;
        if (n == 0) return 1;             // base case: 0! = 1
        return n * fact(n - 1);
    }

    static long fib(int n) {              // two calls per level: O(2^n) — the same values recomputed
        calls++;
        if (n == 0 || n == 1) return n;   // two base cases
        return fib(n - 1) + fib(n - 2);
    }

    public static void main(String[] args) {
        for (int n : new int[]{5, 10}) {
            calls = 0;
            long r = fact(n);
            System.out.println("fact(" + n + ") = " + r + " in " + calls + " calls");
        }
        for (int n : new int[]{5, 10, 20}) {
            calls = 0;
            long r = fib(n);
            System.out.println("fib(" + n + ") = " + r + " in " + calls + " calls");
        }
    }
}

JavaScript

let calls = 0;

function fact(n) {                // one call per level: O(n)
    calls++;
    if (n === 0) return 1;        // base case: 0! = 1
    return n * fact(n - 1);
}

function fib(n) {                 // two calls per level: O(2^n) — the same values recomputed
    calls++;
    if (n === 0 || n === 1) return n;   // two base cases
    return fib(n - 1) + fib(n - 2);
}

for (const n of [5, 10]) {
    calls = 0;
    const r = fact(n);
    console.log(`fact(${n}) = ${r} in ${calls} calls`);
}
for (const n of [5, 10, 20]) {
    calls = 0;
    const r = fib(n);
    console.log(`fib(${n}) = ${r} in ${calls} calls`);
}

Output

fact(5) = 120 in 6 calls
fact(10) = 3628800 in 11 calls
fib(5) = 5 in 15 calls
fib(10) = 55 in 177 calls
fib(20) = 6765 in 21891 calls

Time fact: O(n); naive fib: O(φⁿ) ≈ O(1.618ⁿ) · Space O(n) call stack for both

Tail recursion

Compare the two print functions from the notes. In the first the call is in tail position; in the second the print runs after the call returns, so the frame must be kept alive — it is not tail recursive even though the code looks almost identical.

Python

def fun_tail(n):
    if n == 0:
        return
    print(n, end=" ")
    fun_tail(n - 1)          # last action: tail recursive

def fun_not_tail(n):
    if n == 0:
        return
    fun_not_tail(n - 1)
    print(n, end=" ")        # work after the call: NOT tail recursive

print("tail recursive (print, then recurse):", end=" ")
fun_tail(5)
print()
print("not tail recursive (recurse, then print):", end=" ")
fun_not_tail(5)
print()

C++

#include <iostream>
using namespace std;

void funTail(int n) {
    if (n == 0) return;
    cout << n << " ";
    funTail(n - 1);            // last action: tail recursive
}

void funNotTail(int n) {
    if (n == 0) return;
    funNotTail(n - 1);
    cout << n << " ";          // work after the call: NOT tail recursive
}

int main() {
    cout << "tail recursive (print, then recurse): ";
    funTail(5);
    cout << "\n";
    cout << "not tail recursive (recurse, then print): ";
    funNotTail(5);
    cout << "\n";
}

Java

public class Main {
    static void funTail(int n) {
        if (n == 0) return;
        System.out.print(n + " ");
        funTail(n - 1);            // last action: tail recursive
    }

    static void funNotTail(int n) {
        if (n == 0) return;
        funNotTail(n - 1);
        System.out.print(n + " ");  // work after the call: NOT tail recursive
    }

    public static void main(String[] args) {
        System.out.print("tail recursive (print, then recurse): ");
        funTail(5);
        System.out.println();
        System.out.print("not tail recursive (recurse, then print): ");
        funNotTail(5);
        System.out.println();
    }
}

JavaScript

let line = "";

function funTail(n) {
    if (n === 0) return;
    line += n + " ";
    funTail(n - 1);            // last action: tail recursive
}

function funNotTail(n) {
    if (n === 0) return;
    funNotTail(n - 1);
    line += n + " ";           // work after the call: NOT tail recursive
}

line = "tail recursive (print, then recurse): ";
funTail(5);
console.log(line.trim());
line = "not tail recursive (recurse, then print): ";
funNotTail(5);
console.log(line.trim());

Output

tail recursive (print, then recurse): 5 4 3 2 1
not tail recursive (recurse, then print): 1 2 3 4 5

Time O(n) both · Space O(n) stack — O(1) for the tail version only if the compiler optimises tail calls

Function	Tail recursive?	Why
print `N..1` (print, then call)	yes	the call is the last statement
print `1..N` (call, then print)	no	prints after the call returns
`fact(n) = n * fact(n − 1)`	no	the multiplication happens after the call
`fact(n, acc) = fact(n − 1, n * acc)`	yes	the multiplication is done before the call, in the argument
Quick sort (second call)	yes	sort the left part, then the last action is sorting the right part
Merge sort, post-order traversal	no	work (merge / visit the node) happens after the calls return
Binary search (recursive)	yes	returns the result of the single recursive call

A non-tail function can often be made tail-recursive by carrying the partial result in an accumulator parameter — the multiplication moves from after the call to before it:

Python

def fact(n):                       # not tail recursive: multiplies after the call returns
    if n == 0:
        return 1
    return n * fact(n - 1)

def fact_tail(n, acc=1):           # tail recursive: the running product travels in acc
    if n == 0:
        return acc
    return fact_tail(n - 1, n * acc)   # nothing left to do after this call

for n in (5, 10):
    print(f"fact({n}) = {fact(n)}")
    print(f"fact_tail({n}, 1) = {fact_tail(n)}")

C++

#include <iostream>
using namespace std;

long long fact(int n) {                    // not tail recursive: multiplies after the call returns
    if (n == 0) return 1;
    return n * fact(n - 1);
}

long long factTail(int n, long long acc) { // tail recursive: the running product travels in acc
    if (n == 0) return acc;
    return factTail(n - 1, n * acc);       // nothing left to do after this call
}

int main() {
    for (int n : {5, 10}) {
        cout << "fact(" << n << ") = " << fact(n) << "\n";
        cout << "fact_tail(" << n << ", 1) = " << factTail(n, 1) << "\n";
    }
}

Java

public class Main {
    static long fact(int n) {                  // not tail recursive: multiplies after the call returns
        if (n == 0) return 1;
        return n * fact(n - 1);
    }

    static long factTail(int n, long acc) {    // tail recursive: the running product travels in acc
        if (n == 0) return acc;
        return factTail(n - 1, n * acc);       // nothing left to do after this call
    }

    public static void main(String[] args) {
        for (int n : new int[]{5, 10}) {
            System.out.println("fact(" + n + ") = " + fact(n));
            System.out.println("fact_tail(" + n + ", 1) = " + factTail(n, 1));
        }
    }
}

JavaScript

function fact(n) {                     // not tail recursive: multiplies after the call returns
    if (n === 0) return 1;
    return n * fact(n - 1);
}

function factTail(n, acc = 1) {        // tail recursive: the running product travels in acc
    if (n === 0) return acc;
    return factTail(n - 1, n * acc);   // nothing left to do after this call
}

for (const n of [5, 10]) {
    console.log(`fact(${n}) = ${fact(n)}`);
    console.log(`fact_tail(${n}, 1) = ${factTail(n)}`);
}

Output

fact(5) = 120
fact_tail(5, 1) = 120
fact(10) = 3628800
fact_tail(10, 1) = 3628800

Time O(n) · Space O(n) stack; O(1) with tail-call optimisation

Removing recursion: converting to a loop

Because a tail call passes nothing back, the recursion can be replaced by a loop in two mechanical edits (the original notes' recipe):

Replace if with while
The base-case test if n == 0: return becomes the loop condition while n != 0:.
Update the parameters at the end of the loop body
The tail call fun(n − 1) becomes the assignment n = n − 1 as the last statement.

The two edits that turn a tail call into a loop

tail recursive                         loop
─────────────────────────────          ─────────────────────────────
def fun(n):                            def fun(n):
    if n == 0: return                      while n != 0:
    print(n)                                   print(n)
    fun(n - 1)                                 n = n - 1

A non-tail function cannot be converted this way because the frame must remember what to do after the call. It can still be made iterative with an explicit stack (that is how iterative DFS and in-order traversal work) or, as with factorial, by moving the pending work into an accumulator first.

Python

def print_recursive(n):
    if n == 0:
        return
    print(n, end=" ")
    print_recursive(n - 1)

def print_loop(n):                 # if → while, tail call → parameter update
    while n != 0:
        print(n, end=" ")
        n = n - 1

def sum_recursive(n, acc=0):       # tail recursive with an accumulator …
    if n == 0:
        return acc
    return sum_recursive(n - 1, acc + n)

def sum_loop(n):                   # … becomes a loop with the same accumulator
    acc = 0
    while n != 0:
        acc = acc + n
        n = n - 1
    return acc

print("recursive:", end=" "); print_recursive(5); print()
print("loop:", end=" "); print_loop(5); print()
print("sum of 1..100 recursive:", sum_recursive(100))
print("sum of 1..100 loop:", sum_loop(100))

C++

#include <iostream>
using namespace std;

void printRecursive(int n) {
    if (n == 0) return;
    cout << n << " ";
    printRecursive(n - 1);
}

void printLoop(int n) {                  // if → while, tail call → parameter update
    while (n != 0) {
        cout << n << " ";
        n = n - 1;
    }
}

int sumRecursive(int n, int acc) {       // tail recursive with an accumulator …
    if (n == 0) return acc;
    return sumRecursive(n - 1, acc + n);
}

int sumLoop(int n) {                     // … becomes a loop with the same accumulator
    int acc = 0;
    while (n != 0) { acc = acc + n; n = n - 1; }
    return acc;
}

int main() {
    cout << "recursive: "; printRecursive(5); cout << "\n";
    cout << "loop: "; printLoop(5); cout << "\n";
    cout << "sum of 1..100 recursive: " << sumRecursive(100, 0) << "\n";
    cout << "sum of 1..100 loop: " << sumLoop(100) << "\n";
}

Java

public class Main {
    static void printRecursive(int n) {
        if (n == 0) return;
        System.out.print(n + " ");
        printRecursive(n - 1);
    }

    static void printLoop(int n) {               // if → while, tail call → parameter update
        while (n != 0) {
            System.out.print(n + " ");
            n = n - 1;
        }
    }

    static int sumRecursive(int n, int acc) {    // tail recursive with an accumulator …
        if (n == 0) return acc;
        return sumRecursive(n - 1, acc + n);
    }

    static int sumLoop(int n) {                  // … becomes a loop with the same accumulator
        int acc = 0;
        while (n != 0) { acc = acc + n; n = n - 1; }
        return acc;
    }

    public static void main(String[] args) {
        System.out.print("recursive: "); printRecursive(5); System.out.println();
        System.out.print("loop: "); printLoop(5); System.out.println();
        System.out.println("sum of 1..100 recursive: " + sumRecursive(100, 0));
        System.out.println("sum of 1..100 loop: " + sumLoop(100));
    }
}

JavaScript

function printRecursive(n, parts) {
    if (n === 0) return;
    parts.push(n);
    printRecursive(n - 1, parts);
}

function printLoop(n, parts) {           // if → while, tail call → parameter update
    while (n !== 0) {
        parts.push(n);
        n = n - 1;
    }
}

function sumRecursive(n, acc = 0) {      // tail recursive with an accumulator …
    if (n === 0) return acc;
    return sumRecursive(n - 1, acc + n);
}

function sumLoop(n) {                    // … becomes a loop with the same accumulator
    let acc = 0;
    while (n !== 0) { acc = acc + n; n = n - 1; }
    return acc;
}

let parts = []; printRecursive(5, parts); console.log("recursive:", parts.join(" "));
parts = []; printLoop(5, parts); console.log("loop:", parts.join(" "));
console.log("sum of 1..100 recursive:", sumRecursive(100));
console.log("sum of 1..100 loop:", sumLoop(100));

Output

recursive: 5 4 3 2 1
loop: 5 4 3 2 1
sum of 1..100 recursive: 5050
sum of 1..100 loop: 5050

Time O(n) · Space O(n) recursive, O(1) loop

Tracing recursive functions

Interviews love “what does this print?”. The method: write the calls as a tree, mark what happens before the recursive call (on the way down) and after it (on the way up), then read the output in order. Four puzzles from the notes, solved by the program:

Function	Before the call	After the call	Output for the input	What it computes
print, call `n − 1`, print	`n`	`n`	`4 3 2 1 1 2 3 4`	the sequence down, then mirrored back up
call `n − 1`, print, call `n − 1`	—	`n`, then a second subtree	`1 2 1 3 1 2 1 4 1 2 1 3 1 2 1`	`2ⁿ − 1` numbers — the ruler pattern; `O(2ⁿ)`
`1 + fun(n // 2)` until `n ≤ 1`	—	add 1	`fun(16) = 4`, `fun(13) = 3`	how many times `n` can be halved: `⌊log₂ n⌋`
call `n // 2`, print `n % 2`	—	print the bit	`fun(13) = 1101`	binary representation, most significant bit first

Python

def before_after(n):
    if n == 0:
        return
    print(n, end=" ")             # on the way down
    before_after(n - 1)
    print(n, end=" ")             # on the way up

def double(n):
    if n == 0:
        return
    double(n - 1)
    print(n, end=" ")
    double(n - 1)                 # the whole left subtree printed again

def halvings(n):                  # how many times can n be halved? floor(log2 n)
    if n <= 1:
        return 0
    return 1 + halvings(n // 2)

def binary(n):                    # recurse first so the most significant bit prints first
    if n == 0:
        return
    binary(n // 2)
    print(n % 2, end="")

print("before and after, n = 4:", end=" "); before_after(4); print()
print("double recursion, n = 4:", end=" "); double(4); print()
print("halvings of 16:", halvings(16))
print("halvings of 13:", halvings(13))
print("binary of 13:", end=" "); binary(13); print()
print("binary of 32:", end=" "); binary(32); print()

C++

#include <iostream>
using namespace std;

void beforeAfter(int n) {
    if (n == 0) return;
    cout << n << " ";             // on the way down
    beforeAfter(n - 1);
    cout << n << " ";             // on the way up
}

void doubleRec(int n) {
    if (n == 0) return;
    doubleRec(n - 1);
    cout << n << " ";
    doubleRec(n - 1);             // the whole left subtree printed again
}

int halvings(int n) {             // how many times can n be halved? floor(log2 n)
    if (n <= 1) return 0;
    return 1 + halvings(n / 2);
}

void binary(int n) {              // recurse first so the most significant bit prints first
    if (n == 0) return;
    binary(n / 2);
    cout << n % 2;
}

int main() {
    cout << "before and after, n = 4: "; beforeAfter(4); cout << "\n";
    cout << "double recursion, n = 4: "; doubleRec(4); cout << "\n";
    cout << "halvings of 16: " << halvings(16) << "\n";
    cout << "halvings of 13: " << halvings(13) << "\n";
    cout << "binary of 13: "; binary(13); cout << "\n";
    cout << "binary of 32: "; binary(32); cout << "\n";
}

Java

public class Main {
    static void beforeAfter(int n) {
        if (n == 0) return;
        System.out.print(n + " ");    // on the way down
        beforeAfter(n - 1);
        System.out.print(n + " ");    // on the way up
    }

    static void doubleRec(int n) {
        if (n == 0) return;
        doubleRec(n - 1);
        System.out.print(n + " ");
        doubleRec(n - 1);             // the whole left subtree printed again
    }

    static int halvings(int n) {      // how many times can n be halved? floor(log2 n)
        if (n <= 1) return 0;
        return 1 + halvings(n / 2);
    }

    static void binary(int n) {       // recurse first so the most significant bit prints first
        if (n == 0) return;
        binary(n / 2);
        System.out.print(n % 2);
    }

    public static void main(String[] args) {
        System.out.print("before and after, n = 4: "); beforeAfter(4); System.out.println();
        System.out.print("double recursion, n = 4: "); doubleRec(4); System.out.println();
        System.out.println("halvings of 16: " + halvings(16));
        System.out.println("halvings of 13: " + halvings(13));
        System.out.print("binary of 13: "); binary(13); System.out.println();
        System.out.print("binary of 32: "); binary(32); System.out.println();
    }
}

JavaScript

let out = [];

function beforeAfter(n) {
    if (n === 0) return;
    out.push(n);                  // on the way down
    beforeAfter(n - 1);
    out.push(n);                  // on the way up
}

function doubleRec(n) {
    if (n === 0) return;
    doubleRec(n - 1);
    out.push(n);
    doubleRec(n - 1);             // the whole left subtree printed again
}

function halvings(n) {            // how many times can n be halved? floor(log2 n)
    if (n <= 1) return 0;
    return 1 + halvings(Math.floor(n / 2));
}

function binary(n) {              // recurse first so the most significant bit prints first
    if (n === 0) return;
    binary(Math.floor(n / 2));
    out.push(n % 2);
}

out = []; beforeAfter(4); console.log("before and after, n = 4:", out.join(" "));
out = []; doubleRec(4); console.log("double recursion, n = 4:", out.join(" "));
console.log("halvings of 16:", halvings(16));
console.log("halvings of 13:", halvings(13));
out = []; binary(13); console.log("binary of 13:", out.join(""));
out = []; binary(32); console.log("binary of 32:", out.join(""));

Output

before and after, n = 4: 4 3 2 1 1 2 3 4
double recursion, n = 4: 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1
halvings of 16: 4
halvings of 13: 3
binary of 13: 1101
binary of 32: 100000

Time O(n), O(2ⁿ), O(log n), O(log n) respectively · Space O(n) / O(n) / O(log n) / O(log n) stack

Problem: print 1 to N and N to 1

Python

def print_1_to_n(n):
    if n == 0:
        return
    print_1_to_n(n - 1)         # first everything below n …
    print(n, end=" ")           # … then n: ascending (not tail recursive)

def print_n_to_1(n):
    if n == 0:
        return
    print(n, end=" ")           # n first …
    print_n_to_1(n - 1)         # … then everything below: descending (tail recursive)

for n in (4, 7):
    print(f"1 to {n}:", end=" "); print_1_to_n(n); print()
    print(f"{n} to 1:", end=" "); print_n_to_1(n); print()

C++

#include <iostream>
using namespace std;

void print1ToN(int n) {
    if (n == 0) return;
    print1ToN(n - 1);           // first everything below n …
    cout << n << " ";           // … then n: ascending (not tail recursive)
}

void printNTo1(int n) {
    if (n == 0) return;
    cout << n << " ";           // n first …
    printNTo1(n - 1);           // … then everything below: descending (tail recursive)
}

int main() {
    for (int n : {4, 7}) {
        cout << "1 to " << n << ": "; print1ToN(n); cout << "\n";
        cout << n << " to 1: "; printNTo1(n); cout << "\n";
    }
}

Java

public class Main {
    static void print1ToN(int n) {
        if (n == 0) return;
        print1ToN(n - 1);               // first everything below n …
        System.out.print(n + " ");      // … then n: ascending (not tail recursive)
    }

    static void printNTo1(int n) {
        if (n == 0) return;
        System.out.print(n + " ");      // n first …
        printNTo1(n - 1);               // … then everything below: descending (tail recursive)
    }

    public static void main(String[] args) {
        for (int n : new int[]{4, 7}) {
            System.out.print("1 to " + n + ": "); print1ToN(n); System.out.println();
            System.out.print(n + " to 1: "); printNTo1(n); System.out.println();
        }
    }
}

JavaScript

function print1ToN(n, parts) {
    if (n === 0) return;
    print1ToN(n - 1, parts);    // first everything below n …
    parts.push(n);              // … then n: ascending (not tail recursive)
}

function printNTo1(n, parts) {
    if (n === 0) return;
    parts.push(n);              // n first …
    printNTo1(n - 1, parts);    // … then everything below: descending (tail recursive)
}

for (const n of [4, 7]) {
    let parts = []; print1ToN(n, parts); console.log(`1 to ${n}: ${parts.join(" ")}`);
    parts = []; printNTo1(n, parts); console.log(`${n} to 1: ${parts.join(" ")}`);
}

Output

1 to 4: 1 2 3 4
4 to 1: 4 3 2 1
1 to 7: 1 2 3 4 5 6 7
7 to 1: 7 6 5 4 3 2 1

Time O(n) · Space O(n) call stack

Problem: sum of digits

Python

def sum_of_digits(n):
    if n < 10:                            # base case: a single digit
        return n
    return sum_of_digits(n // 10) + n % 10   # digits of the rest + the last digit

for n in (253, 9, 99999, 1000):
    print(n, "→", sum_of_digits(n))

C++

#include <iostream>
using namespace std;

int sumOfDigits(int n) {
    if (n < 10) return n;                 // base case: a single digit
    return sumOfDigits(n / 10) + n % 10;  // digits of the rest + the last digit
}

int main() {
    for (int n : {253, 9, 99999, 1000})
        cout << n << " → " << sumOfDigits(n) << "\n";
}

Java

public class Main {
    static int sumOfDigits(int n) {
        if (n < 10) return n;                 // base case: a single digit
        return sumOfDigits(n / 10) + n % 10;  // digits of the rest + the last digit
    }

    public static void main(String[] args) {
        for (int n : new int[]{253, 9, 99999, 1000})
            System.out.println(n + " → " + sumOfDigits(n));
    }
}

JavaScript

function sumOfDigits(n) {
    if (n < 10) return n;                               // base case: a single digit
    return sumOfDigits(Math.floor(n / 10)) + (n % 10);  // digits of the rest + the last digit
}

for (const n of [253, 9, 99999, 1000])
    console.log(n, "→", sumOfDigits(n));

Output

Time O(d) — one call per digit · Space O(d) call stack

Problem: palindrome check of a string

palin("aabbaa", 0, 5) — the window shrinks from both ends

s = a a b b a a       start = 0, end = 5   a == a ✓
      a b b a         start = 1, end = 4   a == a ✓
        b b           start = 2, end = 3   b == b ✓
                      start = 3, end = 2   start >= end → True

Python

def is_palindrome(s, start, end):
    if start >= end:                       # 0 or 1 characters left
        return True
    return s[start] == s[end] and is_palindrome(s, start + 1, end - 1)

for s in ["aabbaa", "abcba", "abca", "a", ""]:
    print(s, "→", "Yes" if is_palindrome(s, 0, len(s) - 1) else "No")

C++

#include <iostream>
#include <string>
using namespace std;

bool isPalindrome(const string& s, int start, int end) {
    if (start >= end) return true;         // 0 or 1 characters left
    return s[start] == s[end] && isPalindrome(s, start + 1, end - 1);
}

int main() {
    for (string s : {"aabbaa", "abcba", "abca", "a", ""}) {
        int n = s.size();
        cout << s << " → " << (isPalindrome(s, 0, n - 1) ? "Yes" : "No") << "\n";
    }
}

Java

public class Main {
    static boolean isPalindrome(String s, int start, int end) {
        if (start >= end) return true;     // 0 or 1 characters left
        return s.charAt(start) == s.charAt(end) && isPalindrome(s, start + 1, end - 1);
    }

    public static void main(String[] args) {
        for (String s : new String[]{"aabbaa", "abcba", "abca", "a", ""})
            System.out.println(s + " → " + (isPalindrome(s, 0, s.length() - 1) ? "Yes" : "No"));
    }
}

JavaScript

function isPalindrome(s, start, end) {
    if (start >= end) return true;         // 0 or 1 characters left
    return s[start] === s[end] && isPalindrome(s, start + 1, end - 1);
}

for (const s of ["aabbaa", "abcba", "abca", "a", ""])
    console.log(s, "→", isPalindrome(s, 0, s.length - 1) ? "Yes" : "No");

Output

aabbaa → Yes
abcba → Yes
abca → No
a → Yes
 → Yes

Time O(n) · Space O(n) call stack

Recursion vs iteration

	Recursion	Iteration
Code	mirrors the mathematical definition; short for trees, graphs, divide and conquer	explicit state; short for simple counting
Memory	`O(depth)` call stack, hidden	`O(1)` or an explicit stack you control
Speed	function-call overhead per step	none
Risk	stack overflow on deep input; exponential blow-up without memoisation	off-by-one errors, state bugs
Convertible?	tail recursion → loop mechanically; other recursion → loop + explicit stack	any loop can be written recursively

Interview Q&A

What is a base case and what happens without one?

What is tail recursion and why does it matter?

How do you find the time complexity of a recursive function?

What is the space complexity of a recursive function?

Why is naive recursive Fibonacci slow and how do you fix it?

Direct vs indirect recursion?