When writing programs we usually call different functions to perform a very specific task. We call sqrt to calculate the square root of a number, we call a function max or min to calculate the maximum or the minimum of numbers. Recursion is the process of calling the same function from itself. So, if we have implemented a function with a name f if somewhere in the body of f, we call the function f again (usually with different arguments), that would be a recursive call:
def f(n): # Define a function named f
print(f'f() called with argument {n}') # Print on each call (for demonstration)
if n <= 0: # Stop if n is negative
print('Let\'s stop here...')
else: # Otherwise call f with a smaller number
f(n - 1)
f(10)
This is what the program would print
f() called with argument 10
f() called with argument 9
f() called with argument 8
f() called with argument 7
f() called with argument 6
f() called with argument 5
f() called with argument 4
f() called with argument 3
f() called with argument 2
f() called with argument 1
f() called with argument 0
Let's stop here...
This is a toy example demonstrating how a very basic recursive function could be implemented. In more real-world scenarios, we usually do some computations inside functions and return values after those computations instead of just printing messages.
In algorithmic problems, recursion can be very useful especially when dealing with graphs, advanced sorting algorithms, or backtracking which weβll cover later in the course. Recursive problems are very common, and sometimes itβs much easier to implement a recursive solution than an iterative one using loops.
A video by Reducible - 5 Simple Steps for Solving Any Recursive Problem
The process of solving a large problem by recursively dividing it into smaller problems until reaching the smallest/easiest possible one can be best understood with the concept called βrecursive leap of faithβ.
Recursive Leap of Faith
When implementing a recursive solution to a problem, one usually creates a function that works by calling itself at some point. The part of calling itself is usually referred to as the recursive call.
The great part about recursive solutions is that one can assume that the function works correctly when called with some simple arguments, and then implement the correct behavior for the harder ones. Similar to calling other functions like sqrt, max, abs, etc., you can assume that the function works for some smaller/simpler arguments and call those to build the current result on top of those.
π‘
The only requirement is to make sure the function will arrive at the base case (the simplest case). Otherwise, we would have an infinitely running recursive function and might get a StackOverflow!
As a demonstration of how one might have a computation inside a recursive function, we can try to calculate the sum of all the numbers from 0, 1, 2, β¦, n given a number n.
Letβs implement the sum function step-by-step. The first step is to make sure the function works properly for the simplest case (properly count the sum for n being 0 or 1):
def sum(n):
print(f'sum({n})', end=' -> ')
if n == 0: # In case n is 0 => the sum is 0
return 0 # Stop the function execution here
if n == 1: # In case n is 1 => the sum is 1
return 1 # Stop the function execution here
print(sum(1)) # sum(1) -> 1
print(sum(0)) # sum(0) -> 0
print(sum(2)) # sum(2) -> None (as we haven't implemented this part)
Having this part of the function, we can already use the fact that sum(0) will always correctly return 0, while sum(1) will always return 1. The function will work correctly even if we call the sum function with arguments 0 or 1 from the sum function itself.
So, we can go one step further and implement the sum function for n = 2 and n = 3 by having the results for sum(1) and sum(0):
def sum(n):
print(f'sum({n})', end=' -> ')
if n == 0:
return 0
if n == 1:
return 1
if n == 2: # If n is 2, we can add 2 to the result of sum(1) implemented above
return n + sum(1) # or `n + sum(n - 1)`
if n == 3: # If n is 3, we can add 3 to the result of sum(2) implemented above
return n + sum(2) # or `n + sum(n - 1)`
print(sum(1)) # sum(1) -> 1
print(sum(0)) # sum(0) -> 0
print(sum(2)) # sum(2) -> sum(1) -> 3
print(sum(3)) # sum(3) -> sum(2) -> sum(1) -> 6
print(sum(4)) # sum(4) -> None (as we haven't implemented this part)
This way, itβs obvious that the sum function works properly for small cases like n being equal to 0, 1, 2, or 3.
Having this, we can implement the function for other values of n larger than 3. The only requirement is to arrive at those smaller values of n (0, 1, 2, or 3) when calling the function sum from itself. So, for larger values of n, like 4, 5, or 6, etc. we can implement the sum function by using the fact that to calculate the sum(4), we can add 4 to the result of sum(3), while calculating the sum(5) can be done by adding 5 to the result of sum(4):
def sum(n):
print(f'sum({n})', end=' -> ')
if n == 0:
return 0
if n == 1:
return 1
if n == 2:
return n + sum(1)
if n == 3:
return n + sum(2)
# For all other cases (4, 5, 6, ...)
return n + sum(n - 1)
print(sum(2)) # sum(2) -> sum(1) -> 3
print(sum(3)) # sum(3) -> sum(2) -> sum(1) -> 6
print(sum(4)) # sum(4) -> sum(3) -> sum(2) -> sum(1) -> 10
# ...
The key parts of a recursive function are:
Base case: A condition that stops the recursion. Without this, the function would call itself indefinitely, causing an infinite loop.
Here, it's n == 0 and n == 1.
Recursive step: Where the function calls itself, usually with a different argument.
Here, it's sum(n - 1).
Β
As the calls for n == 1, n == 2, and n == 3 are exactly the same as for n == 4, n == 5, etc., we can even simplify the sum function by having only 1 base case (for n == 0):
This way, having the recursive leap of faith, we assume/know that the function works properly for smaller/simpler cases, and construct the rest of the function based on those simpler cases. That helps in understanding how recursive functions work and how they can be implemented.
π‘
Calling the function recursively is like calling a completely different function that you know for sure will work with the passed arguments.
Challenge
Implement a recursive function that would calculate n! modulo .
Input
The input contains a single integer n (1 β€ n β€ 1000).
Output
The program should print the result of n! modulo .