Basic

Recursion versus a loop

A loop and a recursion can do the same work. The choice is about clarity and safety, not about what is possible.

What you will see

[3, 2, 1]

About 2 min of reading

Quick check

Before this new lesson, one small question about the lesson you just finished. Recall it, do not look it up.

Try It

Compare a loop and a recursion.

Loop sum to 4.

total = 0 for n in range(1, 5): total += n print(total)

Before you run it, say out loud what it will print. Then open the answer.

What it prints

Recursive sum to 4.

def s(n): if n == 0: return 0 return n + s(n - 1) print(s(4))

Before you run it, say out loud what it will print. Then open the answer.

What it prints

Show the recursion limit.

import sys print(sys.getrecursionlimit())

Before you run it, say out loud what it will print. Then open the answer.

What it prints

1000

Recursive reverse.

def rev(a): if not a: return [] return rev(a[1:]) + [a[0]] print(rev([1, 2, 3]))

Before you run it, say out loud what it will print. Then open the answer.

What it prints

[3, 2, 1]

Put it in order

Before you write anything, put these lines back in the right order. Click a line to move it up one step. This support step is easier than writing code from scratch, and it is here to make the last example stick.

Data Flow

A loop and a recursion can do the same work. Recursion suits nested data and risks the stack; a loop suits flat repetition.

1 same work

↓

2 loop keeps state in a variable

↓

3 recursion keeps state in frames

↓

4 match the data shape

Line by line

Read the first example one line at a time. A line that prints shows what appears on screen; the rest set things up quietly.

total = 0 sets nothing on screen

for n in range(1, 5): sets nothing on screen

total += n sets nothing on screen

print(total) 10

Why this works

Same power, different clarity

A loop and a recursion compute the same set of functions. The right one is the one that matches the shape of the data.

Recursion risks the stack

Deep recursion can overflow where a loop cannot. For flat repetition a loop is safer; recursion suits nested structure.

Examples

Same sum, two shapes

total = 0
for n in range(1, 5):
    total += n
print(total)

The loop keeps a running total in one place. The recursion keeps it across frames.

Recursion of the same

def s(n):
    if n == 0:
        return 0
    return n + s(n - 1)
print(s(4))

Same answer as the loop. The state now lives in the call stack.

Loop is safer for deep counts

total = 0
for n in range(100000):
    total += n
print(total)

A loop handles a huge count. The same recursion would overflow the stack.

Recursion fits nested data

def count(a):
    if not a:
        return 0
    return 1 + count(a[1:])
print(count([1, 2, 3]))

When the data nests, recursion follows the shape. A loop needs its own stack.

Depth limit

import sys
print(sys.getrecursionlimit())

Python caps how deep calls nest, around a thousand. Deep recursion hits that cap.

Loop needs an explicit stack

stack = [1, 2, 3]
out = 0
while stack:
    out += stack.pop()
print(out)

To loop over nested data you push a stack yourself. Recursion gets that stack for free.

Pick by clarity

def rev(a):
    if not a:
        return []
    return rev(a[1:]) + [a[0]]
print(rev([1, 2, 3]))

A recursive reverse reads close to the definition. The loop version needs index bookkeeping.

Both are fine

def s(n):
    return n * (n + 1) // 2
print(s(4))

For a flat count, a formula or loop is simplest. Recursion earns its cost only when the shape needs it.

Words this lesson uses

Each one is defined here on this site. Open the entry for the full definition and the other words it points at.

← Counting down and up

Previous Lesson

Counting down and up

Next Lesson

The call stack

The call stack →