Skip to main content
CodePeet

CodePeet 444 Complete DSA Sheet

Introduction to Recursion

Editorial

A function that calls itself

Print 3, 2, 1 without a loop. A function that prints 3 can hand the rest, 2 and 1, to a call of itself; that call prints 2 and hands over 1; and a call with nothing left to print stops. A function that calls itself is recursive, and two things make one work:

  1. A base case: an input small enough to answer without another call.
  2. A smaller call: every other input calls the function on something smaller, closer to the base case.

Each call waits for the one it made, and the computer keeps the waiting calls in a stack, one frame per call. This lesson shows what goes on that stack, why the place of a print decides the order of the output, how a value travels back, and how deep each language lets you go on our judge.

An open-topped stack holding four frames, total(3) at the bottom, then total(2) and total(1), each reading n + ? (3 + ?, 2 + ?, 1 + ?), and total(0) on top in green reading returns 0. Up the left side, blue arrows climb from each frame to the one above it, with pills reading calls total(2), calls total(1) and calls total(0). Down the right side, green arrows carry each answer to the frame below: 0 into total(1), 1 + 0 = 1 into total(2), 2 + 1 = 3 into total(3), and from total(3) a last arrow with 3 + 3 = 6 to a ticked card under the stack reading total(3) returns 6. Focal line: each frame waits for the answer above it. Title: each call waits for the one it made.

A base case and a smaller call

down(n) prints n, then calls itself on n − 1. The calls go 3, 2, 1, 0, and 0 is the base case: it returns without another call, so the chain stops:

void down(int n) {
    if (n == 0) return;         // the base case: stop
    cout << n << "\n";
    down(n - 1);                // a smaller call
}

// down(3) prints 3, 2, 1
def down(n):
    if n == 0:                  # the base case: stop
        return
    print(n)
    down(n - 1)                 # a smaller call

# down(3) prints 3, 2, 1
static void down(int n) {
    if (n == 0) return;         // the base case: stop
    System.out.println(n);
    down(n - 1);                // a smaller call
}

// down(3) prints 3, 2, 1
function down(n) {
    if (n === 0) return;        // the base case: stop
    console.log(n);
    down(n - 1);                // a smaller call
}

// down(3) prints 3, 2, 1

Take away the base case and nothing stops the calls; make the call on n instead of n − 1 and it never gets closer. Both run until the language runs out of room for calls, as the bugs below show.

Each call gets its own frame

When down(3) calls down(2), down(3) isn't finished: it waits at its call, and its own n, 3, waits with it. down(2) gets a fresh frame with an n of its own, 2, so the two never mix. The frames sit on the call stack, newest on top, and only the top one runs. When a call returns, its frame comes off and the call under it carries on from the line after its call.

So down(3) makes four frames at its deepest, n = 3, 2, 1 and 0, then they come off in the opposite order: 0 first, 3 last.

Before the call or after it

Move the print below the call and the order turns around. up(n) calls itself first and prints afterwards, so nothing prints until the base case is reached; then each frame prints its own n as it comes off, smallest first:

void up(int n) {
    if (n == 0) return;
    up(n - 1);                  // first everything below n
    cout << n << "\n";          // then n, on the way back
}

// up(3) prints 1, 2, 3
def up(n):
    if n == 0:
        return
    up(n - 1)                   # first everything below n
    print(n)                    # then n, on the way back

# up(3) prints 1, 2, 3
static void up(int n) {
    if (n == 0) return;
    up(n - 1);                  // first everything below n
    System.out.println(n);      // then n, on the way back
}

// up(3) prints 1, 2, 3
function up(n) {
    if (n === 0) return;
    up(n - 1);                  // first everything below n
    console.log(n);             // then n, on the way back
}

// up(3) prints 1, 2, 3
Two panels, each the path of the calls from n = 3 down to the base case 0 and back up: circles 3, 2, 1, 0 going down to the right, then 1, 2, 3 coming back up. Left panel, code print(n) over down(n - 1): the circles 3, 2 and 1 on the way down are red, a pill reads on the way down, and down(3) prints the tiles 3, 2, 1. Right panel, code up(n - 1) over print(n): the circles 1, 2 and 3 on the way back are red, a pill reads on the way back, and up(3) prints the tiles 1, 2, 3. Focal line: move the print, and the order turns around. Title: where the print sits decides the order.

Work before the call runs on the way down; work after it runs on the way back. Do both and you get the way down and the way back, the shape of Number Series Without Loops:

void both(int n) {
    if (n == 0) {
        cout << 0 << "\n";
        return;
    }
    cout << n << "\n";          // on the way down
    both(n - 1);
    cout << n << "\n";          // and on the way back
}

// both(3) prints 3, 2, 1, 0, 1, 2, 3
def both(n):
    if n == 0:
        print(0)
        return
    print(n)                    # on the way down
    both(n - 1)
    print(n)                    # and on the way back

# both(3) prints 3, 2, 1, 0, 1, 2, 3
static void both(int n) {
    if (n == 0) {
        System.out.println(0);
        return;
    }
    System.out.println(n);      // on the way down
    both(n - 1);
    System.out.println(n);      // and on the way back
}

// both(3) prints 3, 2, 1, 0, 1, 2, 3
function both(n) {
    if (n === 0) {
        console.log(0);
        return;
    }
    console.log(n);             // on the way down
    both(n - 1);
    console.log(n);             // and on the way back
}

// both(3) prints 3, 2, 1, 0, 1, 2, 3

Returning a value

total(n) adds up 1 to n: total(3) is 1 + 2 + 3 = 6. The base case answers 0. Every other call can't answer until its smaller call does: total(3) is 3 + total(2), so it calls and waits. total(0) returns 0 to total(1), which works out 1 + 0 and returns 1 to total(2), which returns 3 to total(3), which returns 6. A value goes back one frame at a time, only to the call that asked for it:

long long total(int n) {
    if (n == 0) return 0;       // the base case answers at once
    return n + total(n - 1);    // waits for the smaller call, then adds n
}

// total(3) returns 6, total(10) returns 55
def total(n):
    if n == 0:                  # the base case answers at once
        return 0
    return n + total(n - 1)     # waits for the smaller call, then adds n

# total(3) returns 6, total(10) returns 55
static long total(int n) {
    if (n == 0) return 0;       // the base case answers at once
    return n + total(n - 1);    // waits for the smaller call, then adds n
}

// total(3) returns 6, total(10) returns 55
function total(n) {
    if (n === 0) return 0;      // the base case answers at once
    return n + total(n - 1);    // waits for the smaller call, then adds n
}

// total(3) returns 6, total(10) returns 55

Step through the call stack

Pick a function and an n, then step through it: the code line running now, the frames on the stack, and what has printed or returned. Before each value appears, say which it will be; the top frame always has the answer.

Call Stack: predict each value, then see it

Returning a list, as the problems do

The practice problems ask you to return the numbers instead of printing them. Pass one list down through the calls and add to it where the print was: after the call, so 1 to n come out in order:

void oneTo(int n, vector<int>& out) {   // &: every call fills the same vector
    if (n == 0) return;
    oneTo(n - 1, out);          // first 1 to n - 1
    out.push_back(n);           // then n
}

vector<int> print1ToN(int n) {
    vector<int> out;
    oneTo(n, out);
    return out;
}

// print1ToN(5) returns [1, 2, 3, 4, 5]
def one_to(n, out):
    if n == 0:
        return
    one_to(n - 1, out)          # first 1 to n - 1
    out.append(n)               # then n

def print_1_to_n(n):
    out = []
    one_to(n, out)
    return out

# print_1_to_n(5) returns [1, 2, 3, 4, 5]
static void oneTo(int n, List<Integer> out) {
    if (n == 0) return;
    oneTo(n - 1, out);          // first 1 to n - 1
    out.add(n);                 // then n
}

static List<Integer> print1ToN(int n) {
    List<Integer> out = new ArrayList<>();
    oneTo(n, out);
    return out;
}

// print1ToN(5) returns [1, 2, 3, 4, 5]
function oneTo(n, out) {
    if (n === 0) return;
    oneTo(n - 1, out);          // first 1 to n - 1
    out.push(n);                // then n
}

function print1ToN(n) {
    const out = [];
    oneTo(n, out);
    return out;
}

// print1ToN(5) returns [1, 2, 3, 4, 5]

Every call adds to the same list, because the list is passed, not copied: Python, Java and JavaScript do that by themselves, and in C++ the & does it. Add before the call instead and the list comes out n down to 1, the order print N to 1 using recursion asks for.

How deep it can go

A recursion n calls deep holds n frames at once, and each language caps how many fit. The deepest total(n) our judge ran, each language at its defaults:

LanguageDeepest that ranDeeper than that
Python997RecursionError: a limit of 1,000 calls
Java10,000 to 11,526 over 3 runsStackOverflowError: the stack is full
JavaScript10,450RangeError: the stack is full
C++100,000,000, the most triedno stack used up: that many frames can't fit in memory, so the compiler made it a loop

Two problems in this group go past Python's limit: Recursion via Repeated Printing asks for n up to 1,000, and Sum of First N Natural Numbers for n up to 10,000; a recursion 1,000 or 10,000 calls deep raised RecursionError on our judge. Raising the limit at the top of a Python solution fixes both:

import sys
sys.setrecursionlimit(20_000)      # room for 10,000 calls, and the judge's own

def total(n):
    if n == 0:
        return 0
    return n + total(n - 1)

print(total(10_000))

It printed 50,005,000.

10,000 calls is near the edge in Java and JavaScript too. JavaScript ran total(10_000) in all 3 runs, about 450 calls short of its limit, and Node sets that limit when it starts (JavaScript for DSA). Java ran it in 4 of 5 runs, with a limit that moved between 10,000 and 11,526 from run to run; Java for DSA shows how to give a recursion a bigger stack. C++ didn't stop this recursion at all, because the compiler made it a loop; it can't do that for every recursion, and C++ for DSA measured where a real one ran out.

Every function in this lesson could be a loop, which keeps one frame however long it runs: O(1) space against recursion's O(n). Recursion earns its place when the problem nests: trees, input inside brackets, and the choices of backtracking, where Thinking Recursively picks up.

Bugs that cost a submission

A step that jumps over the base case.

def skip(n):
    if n == 0:
        return
    print(n)
    skip(n - 2)                 # 3, 1, -1, -3, ...: never 0

skip(3)

It printed 3, 1, −1, −3 and on, then raised RecursionError: counting down by 2 from an odd number jumps over 0, so the base case never runs. if n <= 0: catches every number at or below 0, and the same call then printed 3, 1 and stopped.

A panel titled skip(n - 2), from skip(3): a number line from 3 on the left down to −5 on the right, with red dots on 3, 1, −1, −3 and −5 and red arcs hopping two at a time from each to the next, the last one dashed and followed by an ellipsis. 0 is circled in green with a pill reading n == 0: never landed on, and a red pill over the hop from 1 to −1 reads jumps over 0. Below, a crossed card reads if n == 0:, 3, 1, −1, −3, … never stops, RecursionError; a ticked card reads if n <= 0:, prints 3 and 1, then n = −1 stops it. Focal line: the base case must catch every value the calls land on. Title: the base case has to be reached.

n-- in the call.

function down(n) {
    if (n === 0) return;
    console.log(n);
    down(n--);                  // n-- hands over n, then lowers it
}

down(3);

It printed 3 over and over, then threw RangeError: n-- hands the call the old n and lowers it afterwards, so every call gets 3 again. The same happens in Java and C++. Write down(n - 1).

A recursive call whose answer is dropped.

def total(n):
    if n == 0:
        return 0
    n + total(n - 1)            # worked out, then thrown away

print(total(3))

It raised TypeError: total(1) worked out 1 + 0 and threw it away, so it returned nothing, None in Python, and total(2) tried to add 2 and None. Every path through a function that answers needs a return.

Check yourself

Quiz

1 / 6

Multiple choice

up(n) calls up(n - 1) first and prints n after it. What does up(3) print?

Practice problems

This group's problems, in order:

  1. Recursion via Repeated Printing, print 1 to N using recursion and print N to 1 using recursion: the number added after the call or before it.
  2. Number Series Without Loops: work on both sides of the call.
  3. Sum of First N Natural Numbers and Computing Factorial Recursively: a value returned through every frame. In Python, raise the limit for n = 10,000.
  4. Reverse an Array using recursion: swap the two ends, then the middle is the smaller call.
  5. Power of a Number Using Recursion, Sum of Digits Using Recursion, Reverse a String Using Recursion and GCD Using Recursion: one smaller call each.

Thinking Recursively, in Recursion & Backtracking, builds on this: trusting the smaller call to do its part.