🎓 A1Learner
🔍
0 of 47 lessons completed

Finding the Recurrence

Finding the recurrence is the task of writing the rule that builds an answer from smaller answers of the same problem. Dynamic programming is the method that solves a problem by reusing those smaller answers.

The recognition signal

A problem needs a recurrence when it asks for a count, a lowest cost, or a highest value built step by step. The signals below point to that shape.

signals = [
    "Count the ways to reach a target.",
    "Find the lowest cost to reach a step.",
    "Find the highest value from a set of choices.",
]
for s in signals:
    print("Signal: " + s)

The recurrence template

Climbing stairs allows steps of 1 or 2. The ways to reach step n equal the ways to reach step n minus 1 plus the ways to reach step n minus 2.

def ways(n):
    if n <= 1:
        return 1
    return ways(n - 1) + ways(n - 2)


print("Ways to climb 5 steps:", ways(5))

Worked problem: steps of 1, 2, or 3

With steps of 1, 2, or 3, the ways to reach step n equal the sum of the ways to reach the three steps below it. The base cases are one way for step 0 and step 1, and two ways for step 2.

def ways(n):
    if n == 0:
        return 1
    if n == 1:
        return 1
    if n == 2:
        return 2
    return ways(n - 1) + ways(n - 2) + ways(n - 3)


print("Ways to climb 4 steps:", ways(4))

Example

nums = [2, 7, 9, 3, 1]


def best(i):
    if i < 0:
        return 0
    if i == 0:
        return nums[0]
    return max(best(i - 1), best(i - 2) + nums[i])


print("Best total:", best(4))

Key points

  • A recurrence is a rule that defines an answer from smaller answers of the same problem.
  • Use the recurrence to shrink a problem one step at a time until it reaches a base case.
  • A base case is the smallest input with a directly known answer.
  • Finding the recurrence turns a big problem into a chain of smaller copies of itself.

Each house is either skipped or taken. Skipping house i keeps the best total up to house i minus 1. Taking it adds its value to the best total up to house i minus 2. The best total for the five houses is 12, from houses worth 2, 9, and 1.

Note

the recurrence must name smaller inputs only, or the shrinking never ends.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

Exercise

Stairs allow steps of 1 or 2. Which rule gives the ways to reach step n?