Recursion is a method used to solve a computational problem by dividing a problem into multiple smaller sub-problems similar to the original problem and by solving each problem independently. Eventually, we come to a state where the divided problem is small enough that the answer to it is straightforward.
Dividing a problem into similar sub-problems
Let’s consider the problem where we need to find factorial of a number. (Factorial of a number ‘n’ is equal to n * n-1 * n-2 * n-3 … 1. For example, factorial of number 4 is equal to 4 * 3 * 2 * 1 = 24). In order to solve this problem recursively, we need to first be able to divide the original problem into one or more subproblems of smaller size than the original problem.
Let’s say the original problem is to find factorial of a number n, let’s represent the corresponding function with get_factorial(n).
This function can also be written as get_factorial(n) = n * get_factorial(n-1).
Now the overall function which can give us the factorial of a number can be as simple as:
fun get_factorial(num):
return num * get_factorial(num - 1)
And this is what happens if we pass number 3 to the above function:
get_factorial(4) = 4 * get_factorial(3)
get_factorial(3) = 3 * get_factorial(2)
get_factorial(2) = 2 * get_factorial(1)
and so on...
So we have a single function get_factorial which takes in a number, divides into smaller sum problem which can be solved with the same function and then call the same function! This might sound complicated or sketchy at the first glance, but you will get used to this after looking a couple of recursive functions.
Base case(s) of a recursive function
In the above example everything might seem okay at the first glance. But upon looking closely, we find that the recursion (division) goes on and on:
get_factorial(4) = 4 * get_factorial(3)
get_factorial(3) = 3 * get_factorial(2)
get_factorial(2) = 2 * get_factorial(1)
get_factorial(1) = 1 * get_factorial(0)
get_factorial(0) = 0 * get_factorial(-1)
and so on...
From definition of factorial we know for sure that get_factorial(1) is equal to 1 and so we need not call the recursive function again. This is called the base case of recursion and this helps in preventing a function call itself again and again infinitely. This is how the final factorial function looks after the base condition is added:
fun get_factorial(num):
if num == 1, return 1 # Base Case
else return ( num * get_factorial(num - 1) )
A recursive function can have more than 1 base case depending on the complexity of the original problem.
TODO: Add fibonacci example and other interactive I/O examples.