Lessons · Python · a function that calls itself

A problem defined by a smaller version of itself

A recursive function calls itself on a smaller input, and has a base case that stops it.

Hone is a place to practise programming. This is one of its lessons, written out in full and free to read without an account.

What it is for

Trees, folders inside folders, nested JSON, 'ways to climb the stairs': structures and problems that repeat inside themselves are natural to walk recursively.

How to think about it

Two questions. What is the smallest case where I just know the answer? That is the base. Given the answer for a smaller input, how do I build the answer for this one? That is the step.

Worked example

def count_down(n):

Print n, n-1, ..., 1.

    if n == 0:

Base case: nothing to print.

        return

Stop.

    print(n)

Do this level's work.

    count_down(n - 1)

Then the smaller problem. Every call moves toward the base.

Your turn

Sum a list recursively.

def total(xs):
    if not xs:
        return 0
    return xs[0] + total(xs[:])

The trap

A step that does not shrink the input, or a base case that is never reached. Python stops you at about 1,000 calls with RecursionError.

Practise a function that calls itself on HoneA question on it now, a coding challenge where there is one, and it is remembered for review. Free, no email needed.