BlogsDope image BlogsDope

Common examples of loops using recursion in Python

May 21, 2017 PYTHON EXAMPLE RECURSION 3896

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 the else is n+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.


Liked the post?
Developer and founder of CodesDope.
Editor's Picks
0 COMMENT

Please login to view or add comment(s).