All courses › Intermediate Programming › Recursion

Recursion

A recursive function calls itself on a smaller problem, and needs a base case to stop the chain of calls. Without a base case, the function ends in a RecursionError because the calls never stop.

f(n)=n⋅f(n−1),  f(1)=1f(n) = n\cdot f(n-1),\ \ f(1) = 1factorial: recursive step and base case

Symbols

nnthe problem size

Example

def fak(n):

if n <= 1: return 1

return n * fak(n - 1)

fak(3) gives 3⋅2⋅1=63\cdot 2\cdot 1 = 6.

Always write the base case first — it is what guarantees the recursion actually stops.
Practise algorithms and data structures for free →

← Time complexity, O-notation · Stack and queue →

Part of Intermediate Programming: Algorithms and data structures.