Recursion is simply defined as repeating some procedure until you can’t anymore. In computing, it is used to solve problems by breaking them into smaller parts by using a function that passes parameters to itself.
For each recursive function to work, 2 key elements are needed
a stopping condition (base case): This is the smallest simplest solution to the problem
at least one recursive call (recursive step): represent the problem reduced by some margin
Take note that any problem that can be solved using recursion can also be solved non-recursively. It is preferably to use a non-recursive solution to a problem if the problem size is very big because this can have a negative impact on the performance of the computer especially the memory.
To understand recursion, you need to understand the problem and estimate its size and impact on the performance of your computer. If your computer can handle the problem, determine if it can be solved recursively and establish its base case. If you know the base case, then the recursive step is simply a call to the function using a smaller parameter.
Think of a function to find the sum of the first n integers. If n is 5, then the sum is simply 0 + 1 + 2 + 3 + 4 + 5 = 15. A non recursive solution to the problem would require a loop similar to this
def sumOf(s):
sum = 0
for i in range(s+1):
sum += i
return sum
sumOf(5) = 15
If you are to use recursion, you would realise that the base case would have to be when you reach 0 which would indicate that we recursively call the function starting with the biggest parameter and reducing it until you reach 0. If n is 5, you start the recursive call with 5,4,3,2,1,0
def sumOf(s):
# Base case
if s == 0:
return s
# Recursive step
else:
return s + sumOf(s-1)
sumOf(5) = 15
Notice that Python only starts to add the numbers after the base cad has been executed. The whole time the recursive step is executed, the calls not executed are parked on a stack and they are removed one by one until it is empty.
Step 1: sumOf(5)
Step 2: 5 + sumOf(4)
Step 3: 4 + sumOf(3)
Step 4: 3 + sumOf(2)
Step 5: 2 + sumOf(1)
Step 6: 1 + sumOf(0)
Step 7: 0
After step 6, the base case is evaluated and 0 is returned.
Step 6 is then removed from the stack and evaluated as 1 + 0 which equals 1.
Step 5 is then removed from the stack and evaluates as 2 + 1 which equals 3.
Step 4 is then removed from the stack and evaluates as 3 + 3 which equals 6.
Step 3 is then removed from the stack and evaluates as 4 + 6 which equals 10.
Step 2 is then removed from the stack and evaluates as 5 + 10 which equals 15.
Since the stack is empty, the function stops executing and the final solution is 15.
If you were to find the length of a string, you would simply just use len(“String”) which would give the answer of 6. You could also do this recursively by slicing the string until it has a length of 0 with a recursive function that looks like this
def length(s):
# Base case: empty string
if s == '':
return 0
# Recursive step: slice of the first character
else:
return 1 + length(s[1:])
Python shell evaluation of the function
length('') = 0
length('star') = 4
length('python') = 6
length('yes') = 3
length('1') = 1
A recursive function to find the factorial(n) in Python would have a base case that gives a solution of 1 when n is 0 or when n is 1 because 0! = 1! = 1
The recursive function would look like this
def factorial(n):
# Base case:
if n == 0 or n == 1:
return 1
# Recursive step
else:
return n * factorial(n-1)
Evaluating the function in the Python shell produces
factorial(0) = 1
factorial(1) = 1
factorial(2) = 2
factorial(3) = 6
factorial(4) = 24
factorial(5) = 120
Share your thoughts