DSA What Is Recursion
Recursion is a method where a function calls itself on a smaller problem. A base case is the smallest problem that the function answers directly.
A countdown that calls itself
The base case here is n equal to zero, where the function stops. Every other call prints its number and calls itself with one less.
def countdown(n):
if n == 0:
print("Blast off")
return
print(n)
countdown(n - 1)
countdown(3)Factorial and its base case
Factorial of n means n multiplied by every whole number below it down to one. The answer for zero is one, and that fact is the base case here.
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)
print(factorial(4))
print(factorial(0))Each call gets a smaller input
The print shows the argument of every call in order. The argument drops by one each time until the base case answers it.
def factorial(n):
print("factorial called with", n)
if n == 0:
return 1
return n * factorial(n - 1)
print(factorial(3))Example
def factorial(n, depth=0):
print(" " * depth + "call factorial(" + str(n) + ")")
if n == 0:
print(" " * depth + "return 1")
return 1
result = n * factorial(n - 1, depth + 1)
print(" " * depth + "return " + str(result))
return result
def countdown(n, depth=0):
print(" " * depth + "call countdown(" + str(n) + ")")
if n == 0:
print(" " * depth + "done")
return
countdown(n - 1, depth + 1)
factorial(4)
countdown(3)Key points
- A recursive function solves a big problem by calling itself on a smaller one.
- The base case stops the calls from going on forever.
- Each call works on a smaller input than the call before it.
In this example, indentation shows how deep each call sits inside the calls before it. The factorial calls sink down to the base case at zero, which returns one. The returns then climb back up, and each call multiplies its own number in. The countdown shows the same sinking shape, ending at its own base case.
Try it Yourself
Edit the code, then press Run.
Running is simulated · Python Playground
Exercise
A recursive function keeps calling itself on smaller inputs. What must it have so the calls eventually stop?