DailyRNG
Login
Advanced

Cost of a recurrence

A recursive cost is written as a recurrence: the work at one call plus the calls it makes. Solving the recurrence names the class.

What you will see

32

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

Solve a recurrence by counting calls.

1

One smaller call, n of 5.

def work(n): if n <= 1: return 1 return 1 + work(n - 1) print(work(5))

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

What it prints
5
2

Two half calls, n of 8.

def work(n): if n <= 1: return 1 return 1 + work(n // 2) + work(n // 2) print(work(8))

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

What it prints
15
3

Halve and combine, n of 8.

def work(n): if n <= 1: return 1 return n + work(n // 2) print(work(8))

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

What it prints
15
4

Two half calls with work, n of 8.

def work(n): if n <= 1: return 1 return n + work(n // 2) + work(n // 2) print(work(8))

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

What it prints
32

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

Recursive cost is a recurrence: work per call plus the calls made. Depth sets the stack and branching sets the total.
1 write work per call
↓
2 count the calls made
↓
3 solve the recurrence
↓
4 name the class
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.

def work(n): sets nothing on screen
if n <= 1: sets nothing on screen
return 1 sets nothing on screen
return 1 + work(n - 1) sets nothing on screen
print(work(5)) 5
Why this works
Write the recurrence

The cost of recursion is the work at one node plus the cost of the calls it makes. That equation is the plan.

Depth and branching

A shallow tree with many branches can still be huge. Depth sets the stack, branching sets the total.

Examples

One smaller call

def work(n):
    if n <= 1:
        return 1
    return 1 + work(n - 1)
print(work(5))

One call to n minus one plus one step. The chain is n deep, so the cost is linear.

Two half calls

def work(n):
    if n <= 1:
        return 1
    return 1 + work(n // 2) + work(n // 2)
print(work(8))

Two calls to half the size plus one step. That is a tree of depth log n.

Halve and combine

def work(n):
    if n <= 1:
        return 1
    return n + work(n // 2)
print(work(8))

One half call plus n work at the top. The levels add to about 2n, so linear.

Two half calls with work

def work(n):
    if n <= 1:
        return 1
    return n + work(n // 2) + work(n // 2)
print(work(8))

Two half calls plus n work. Each level costs n and there are log n levels, so n log n.

Count the calls

calls = 0
def work(n):
    global calls
    calls += 1
    if n <= 1:
        return
    work(n - 1)
work(5)
print(calls)

Counting the calls is the same as solving the recurrence. Five deep gives five calls.

Depth sets the stack

def depth(n):
    if n <= 1:
        return 0
    return 1 + depth(n // 2)
print(depth(64))

The depth of the tree is the stack height. Halving to one gives a depth of six.

Branching is costly

def work(n):
    if n <= 1:
        return 1
    return 1 + work(n - 1) + work(n - 1)
print(work(4))

Two calls to n minus one doubles each level. That tree is exponential.

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.

← Trading time for space
Previous Lesson
Trading time for space
Next Lesson
Amortized cost
Amortized cost →