How do I explain recursion using factorial and Fibonacci in Python?

Recursion means a function calls itself to solve a smaller version of the same problem. A recursive solution must have a base case; otherwise the function keeps calling itself until the program fails.

What the question is asking

The task is testing whether you understand the base case, recursive case, call stack and efficiency. Factorial is a simple example because each call reduces the number by one. Fibonacci is useful because it shows why some recursive solutions are inefficient.

Key concepts to cover

• Base case
• Recursive case
• Call stack
• Return value
• Stack overflow or recursion limit
• Time complexity
• Memoisation

Mini examples

textfactorial(n):
  if n == 0:
    return 1
  return n * factorial(n - 1)

For factorial(4), the function calculates 4 x factorial(3), then 3 x factorial(2), then 2 x factorial(1), then reaches factorial(0).

Naive Fibonacci is less efficient:

textfib(n):
  if n <= 1:
    return n
  return fib(n - 1) + fib(n - 2)

It repeats many calculations, so memoisation or iteration is usually better for larger values.

Sample questions and short answers

1. What is a base case?

The condition that stops recursion, such as n equals 0 for factorial.

2. Why is Fibonacci slower than factorial?

Naive Fibonacci branches into two calls at each step and repeats work. Factorial makes one recursive call per step.

3. What is the call stack?

The call stack stores active function calls until they return.

4. Is recursion always better than loops?

No. Recursion can be elegant, but loops may be more efficient and avoid recursion depth limits.

Common student mistakes

• Forgetting the base case
• Not reducing the input
• Confusing print with return
• Ignoring repeated work in Fibonacci
• Not testing small inputs

Related questions

• Why does my Python function change my list outside the function?
• How do I analyse Big O n log n vs n squared in practice?
• How do I explain stacks, queues and linked lists in a data structures assignment?

Academic use note

Use this guide to explain recursion. If your assignment asks for code, include tested Python functions and explain output for small values.

Sources and further reading

• Python documentation: Functions
• Python documentation: Data structures