Recursion 0/1

Lesson 11 of 21

Recursion

Solve a problem by solving a smaller copy of it.

Part 1 of 8 Base case and recursive case

Recursive definitions

Some things are easiest to describe in terms of a smaller version of themselves. Take the factorial of a whole number nn, written n!n!. It is 1×2×⋯×n1 \times 2 \times \cdots \times n, so 4!=1×2×3×4=244! = 1 \times 2 \times 3 \times 4 = 24. Look at what 4!4! contains: 1×2×31 \times 2 \times 3 is 3!3!, so 4!=4×3!4! = 4 \times 3!. That holds for every nn, which gives a second way to define the factorial, with two rules:

n!=n×(n−1)!and0!=1n! = n \times (n - 1)! \qquad \text{and} \qquad 0! = 1

The first rule works out n!n! from the factorial just below it. On its own it would never finish: 4!4! needs 3!3!, which needs 2!2!, and so on down past 0 into (−1)!(-1)!. The second rule stops the chain by giving one answer outright. (0!=10! = 1 is chosen so that the first rule gives 1!=1×0!=11! = 1 \times 0! = 1.)

A definition like this, which uses a smaller case of the thing being defined, is recursive. A function can work the same way: its body can call the very function being defined.

Definition

A recursive function is a function that calls itself.

The base case and the recursive case

Here are the two rules written as a function:

Sign up to run
def fact(n):
    if n == 0:
        return 1
    return n * fact(n - 1)

print(fact(4))
print(fact(0))

The if is the base case: an input small enough to answer without calling fact again, here n=0n = 0. The last line is the recursive case: it asks fact for (n−1)!(n - 1)! and multiplies the answer by nn. Each call passes an input one smaller than its own, so starting from 4 the calls go 4, 3, 2, 1, 0 and stop.

This AtCoder problem defines a function by exactly these two rules, which makes it a good first recursive program to submit. Read NN with int(input()) and print fact(N):

A function ff is defined on whole numbers x≥0x \ge 0 by two rules: f(0)=1f(0) = 1, and f(k)=k×f(k−1)f(k) = k \times f(k - 1) for every k≥1k \ge 1. Given NN, print f(N)f(N).

Constraints

  • 0≤N≤100 \le N \le 10
  • NN is an integer

Sample 1 · Input

2

Output

2

Sample 2 · Input

3

Output

6

Sample 3 · Input

0

Output

1

Sample 4 · Input

10

Output

3628800

The same function written with a loop

You could also compute a factorial with a while loop. Here are both versions side by side:

Sign up to run
def fact_loop(n):
    result = 1
    k = n
    while k > 0:
        result = result * k
        k = k - 1
    return result

def fact(n):
    if n == 0:
        return 1
    return n * fact(n - 1)

print(fact_loop(5), fact(5))

The loop keeps its progress in two names that change on every pass, result and k. The recursive version never changes a name. Its progress is the chain of calls, each with its own n, and the multiplications happen as those calls return. The next part shows this step by step.

For the factorial, the loop is just as good. Recursion pays off on problems that break into smaller copies of themselves in a way one loop can't follow. Near the end of this lesson you'll print every number with nn digits, where nn comes from the input: loops would need one nested loop per digit, while one recursive function handles any nn.