This article is an extension of the ‘Have your own functions’ chapter of Python. If you need to learn basics then visit the Python course first. You can also practice a good number of questions from practice section.
This is an article on writing the common loop codes using recursion for the better understanding of recursion. So, let’s continue.
Sum of first n natural numbers using recursion
def sum_n(n):
if n == 1:
return n
else:
return n+sum_n(n-1)
print (sum_n(100))
Let’s understand this example by calculating the sum of first 4 natural numbers i.e., sum_n(4)
step by step.
- The condition of ‘if’ is not correct. So, the statements of
else
will get executed.
The value returned in theelse
isn+sum_n(n-1)
i.e., 4+sum_n(3). - Now,
sum_n(3)
will return 3+ sum(2). So, the above expression will become 4+3+sum_n(2). - Similarly,
sum_n(2)
will return 2+sum_n(1) and the expression will become 4+3+2+sum_n(1) . - During
sum_n(1)
, the condition of ‘if’ will get satisfied and 0 will get returned and thus making the final expression 4+3+2+1.
Sum of all the digits of a number using recursion
import math
def sum_digit(n):
#to calculate the number of digits in a number
number_of_digits = int(math.log10(n))+1
if number_of_digits == 1:
return n
else:
return n%10 + sum_digit(n//10)
print (sum_digit(54321))
This example follows the logic that the sum of all the digits of a number 1234 will be 4 + sum of all the digits of the number 123 and again be applying the same logic on 123, it will become 4 + 3 + sum of all the digits of the number 12 then 4 + 3 + 2 + sum of all the digits of the number 1 and finally 4 + 3 + 2 + 1.
This is exactly what we are doing in our code.
int(math.log10(n))+1
will give the number of digits in the number ‘n’.
return n%10 + sum_digit(n//10)
– n%10 is the last digit of the number ‘n’ and n//10 is a number excluding the last digit of the number ‘n’.
Multiplication table using recursion
def mul_table(n, i=1):
print (n*i)
if i != 10:.
mul_table(n,i+1)
mul_table(5)
This is an example of just calling the function ‘mul_table’ inside itself with a different value of ‘i’.
mul_table(n, i=1)
– The default value of ‘i’ is 1. If no value of ‘i’ is given while calling ‘mul_table’ then the value of ‘i’ will be 1.
mul_table(n,i+1)
– This line will call the function ‘mul_table’ with the value of ‘i’ increased by 1. This means that if the value of ‘i’ is 4 (n*4 got printed) then in the next turn, the value of ‘i’ will be 5 and n*5 will get printed.
Calculating the power of one number raised to another using recursion
def power(a,b):
if b == 1:
return a
else:
return a * power(a,b-1)
print (power(5,3))
The logic behind this code is that the ab = a * ab-1. For e.g., 43 = 4*42 = 4*4*41 = 4*4*4.
You can see the examples of Factorial and Fibonacci series here.