Pylerno
English

Recursion

Reduce a problem to a smaller version and identify its stopping condition.

On this page

The concept

Recursion occurs when a function calls itself. Every valid path must eventually reach a base case that does not recurse. For factorial, zero returns one; a larger nonnegative integer reduces the problem by one each time.

The example's contract is a small nonnegative integer. Negative values are rejected; arbitrary floats or very large values are outside this demonstration's intended domain. Python has a recursion-depth limit. A loop is often the simpler choice for a long linear calculation.

Worked example

python
def factorial(number):
    if number < 0:
        raise ValueError("Number must not be negative.")
    if number == 0:
        return 1
    return number * factorial(number - 1)


print(factorial(0))
print(factorial(5))
result = 1
for number in range(1, 6):
    result *= number
print(result)

Trace the result

  1. factorial(0) returns immediately.
  2. factorial(5) descends through smaller inputs before combining their results.
  3. The iterative calculation produces the same 120 without a nested chain of calls.
text
1
120
120
Line-by-line walkthrough

Lines 1–6: def factorial(number):

Define the function factorial with input names number. Definition stores the operation rather than executing its body. An ordinary call executes a normal function; a coroutine runs when awaited/scheduled, and a generator advances when consumed. Decorators can provide a context-manager or wrapper interface. Indented statements below belong to this operation.

Lines 2–3: if number < 0:

Evaluate number < 0. Execute the indented body if it is truthy; otherwise follow the alternative branch, if present. Branch order and indentation are part of the behavior.

Line 3: raise ValueError("Number must not be negative.")

Raise ValueError('Number must not be negative.'). Normal execution stops here unless an enclosing handler catches it. A from cause, when present, preserves the reason for a translated error.

Lines 4–5: if number == 0:

Evaluate number == 0. Execute the indented body if it is truthy; otherwise follow the alternative branch, if present. Branch order and indentation are part of the behavior.

Line 5: return 1

Evaluate 1 and return that value to the caller. This ends the current function call; subsequent statements on this execution path do not run.

Line 6: return number * factorial(number - 1)

Evaluate number * factorial(number - 1) and return that value to the caller. This ends the current function call; subsequent statements on this execution path do not run.

Line 9: print(factorial(0))

Evaluate the print arguments from the current state and display them. sep controls separators and end controls the ending when those options are provided. Displaying a value does not return that value from the surrounding function.

Line 10: print(factorial(5))

Evaluate the print arguments from the current state and display them. sep controls separators and end controls the ending when those options are provided. Displaying a value does not return that value from the surrounding function.

Line 11: result = 1

Evaluate 1, then bind or update result with the result. This literal is prepared example data. Assignment itself does not imply a deep copy.

Lines 12–13: for number in range(1, 6):

Obtain each item from range(1, 6) and bind it to number before executing the body. A tuple-shaped target unpacks that item. A loop else, if present, runs only when completion does not use break.

Line 13: result *= number

Update the current target using result *= number. Trace its value before and after this line; later statements see the updated state.

Line 14: print(result)

Evaluate the print arguments from the current state and display them. sep controls separators and end controls the ending when those options are provided. Displaying a value does not return that value from the surrounding function.

Common mistake

A missing base case or a recursive call that does not reduce the problem eventually fails rather than solving it.

Check your understanding

What does this program print?

python
def f(n):
    if n == 0: return 1
    return n * f(n-1)
print(f(3))
Choose one answer

Search documentation

Share this page