What is Recursion?
Recursion is when a function calls itself to solve a smaller version of the problem.
This continues until the problem becomes small enough that it can be solved directly. That smallest case is called the base case .
Recursion Example
Adding two numbers together is easy to do, but adding a whole range of numbers can be tricky.
Recursion makes it simple: break it down into the task of adding one number at a time.
Runnable example
def sum_range(k):
if k > 0: # base case
return k + sum_range(k - 1)
else:
return 0
result = sum_range(10)
print(result) # 55Example Explained
When sum(10) is called, it adds 10 to the sum of all smaller numbers, like this:
10 + sum(9)
10 + ( 9 + sum(8) )
10 + ( 9 + ( 8 + sum(7) ) )
...
10 + 9 + 8 + 7 + ... + 1 + sum(0)
10 + 9 + 8 + 7 + ... + 1 + 0Since sum(0) just returns 0, the recursion stops and the result is calculated.
Countdown Example
This example prints numbers down from 5 to 1, using recursion:
Runnable example
def countdown(n):
if n == 0: # base case
print("Done!")
else:
print(n)
countdown(n - 1) # recursive call
countdown(5)Factorial Example
The factorial of a number ( n! ) is the product of all numbers from 1 to n.
Example: 5! = 5 * 4 * 3 * 2 * 1 = 120
This can be solved naturally with recursion:
Runnable example
def factorial(n):
if n == 1: # base case
return 1
else:
return n * factorial(n - 1)
print(factorial(5))Summary
- Recursion is when a function calls itself.
- A base case is needed to stop the recursion.
- Recursion is useful for problems that break down into smaller, similar problems (like factorial, traversing folders, tree/graph algorithms).
Note
Recursion is powerful but can use a lot of memory if not carefully written. Always make sure you have a base case , or the recursion may go on forever!