All you want to know about recursion in Python




It is a way of programming or coding technique, in which a function calls itself for one or more times in its body. Usually, it is returning the return value of this function call procedure. If a function definition fulfils such conditions, we can call this function a recursive function.



2 Laws of Recursion

  • Must have a base case - There must be at least one base criteria/condition, when such condition is met the function stops calling itself.

proper recursion

  • Must move toward the base case - The recursive calls should moves in such a way that each time it comes closer to the base criteria.

When there is no base case (aka Exit statement) the program will run forever


Simple algorithms with recursion


def hellomessage():


Program Explanation

Run this will display hello message forever ,because there is nobase case to exit.It call hellomessage() function & Display hello And again call hellomessage() function. This will call hellomessage() function forever and will display hello continuously

To exit press ctrl + c

Sum of Natural Numbers Using Recursive Function


  • Test if n equal to base case return 1.
  • If not, then call the algorithm with n – 1 (so as to move towards base case)


def sum(n):
    if n <= 1:      # The Base Case #
        return n   # of the Problem. #

        return n + sum(n-1) # n-1 makes the function move move towards the base case

num = int(input("Enter a number: "))
print("The sum is: ", sum(num))

Program Explanation

The input() function takes input from the user and int() function converts its type to an integer as input() return string. Here we call sum() function and pass the entered number, which is assigned to n. The base condition for recursion is defined and if the input number is less than or equals to 1, the number is returned, else we return the same function call with number decremented by 1. In this way, the recursive function works in Python that can calculate the sum of natural numbers.It works like suppose we pass 5 in input 5 + sum(4) + sum(3) + sum(3) + 1

Factorial of a Number Using Recursion


  • Test if n <= 0. If so, return 1
  • If not, then call the factorial algorithm with n – 1 and multiply the result by n and return that value.


def factorial(x):
    if x == 1:
        return 1
        return x * factorial(x-1)

f = factorial(5)
print("factorial of 5 is: ",f)

Fibonacci numbers Using Recursion



  • If n = 1 or n = 2, then return 1
  • else
  • a = Fib(n-1)
  • b = Fib(n-2)
  • return a + b


def fib(n):
    if n <= 1:
        return n  # Base Case 
        return(fib(n-1) + fib(n-2))  # n-1 and n-2, Moving towards the base case.

nterms = int(input("enter a number"))

if nterms <= 0:
    print("Plese enter a positive integer")

    print("Fibonacci sequence:")
    for i in range(nterms):


No Comments Yet