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
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
- factorial(0) returns immediately.
- factorial(5) descends through smaller inputs before combining their results.
- The iterative calculation produces the same 120 without a nested chain of calls.
1
120
120Line-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.