Recursion occurs when something is defined in terms of itself. Recursion has applications in many disciplines, but what we focus on here is application in Computer Science. So for our purposes we define a recursion when a function calls itself.
Many algorithms make use of recursion, so it is good the get the grip on this technique.
Every recursive function need to have two cases:
- Base case
- Recursive case
The recursive case occurs when the function keeps calling itself, and the base case occurs when we want to stop the function from calling itself, unwind the stack and return. If a given function would lack the base case, then our function would go into an infinite loop and would crash our program.
The classic recursive example is to calculate a factorial of a given number.
Note: factorial of a positive integer is a product of all positive integers equal to or less than the given integer.
def factorial(number):
if number == 1:
return 1
else:
return number * factorial(number-1)
In this case “if number == 1” statement is our base case which would terminate the recursive calls, unwound the stack and return calculated value. Without it our program would consume all available memory and would crash our program. So it is really important to properly define the base case.
The recursive case is what we see under the “else” branch, which keeps calling itself and multiplying all the numbers, each time decreased by 1. To help to visualise, if we would pass number 5 to the function, all the calls would look like that:
5 * factorial(4) * factorial(3) *
factorial(2) * factorial(1)
which is equal to:
5 * 4 * 3 * 2 * 1
EasyAlgorithms 