← All lessons

Recursion

Sign in · Sign up

Lesson 6.10

A function can call itself. For that to ever end, you need two parts:

  • a base — when to stop;
  • a step — make the value smaller and call yourself again.
def fact(n):
    if ...:                 # base: when to stop
        return 1
    return ...              # step: n times the call with a smaller number

fact(5) is 5 * fact(4), and so on down to fact(1). Without a base the function would call itself forever, and Python would stop it with an error.

Write a function fact(n) that returns the factorial of a number. Assume n is greater than zero.

Hint

Recursion has two parts: the base (when to stop) and a step with a smaller value.

A factorial is n * (n - 1) * ... * 1, and one is the base: return 1. The step calls the function with n - 1 and multiplies the result by n. Without a return in the body the function gives None.