Guide to Write Recursive Functions using Python

Looping is not only the way to express a set of repeating statements in a programming language. There is an interesting and optimistic method for some looping problems. In simple words, the calling of a function inside the same function’s definition is called recursion. This is a wonderful concept to get a compact solution for some problems which can be solved with the help of splitting the problem into sub-problems. In this article, we will learn about the recursion concept and some problems based on the concept. To make the code understandable I have written the solution in both normal looping and recursive functions.

Recursive Function

A recursive function is a function that calls itself in its definition. That function can be called directly or indirectly. In programming, we can have a lot of functions defined by the users. But if one function called by the same function it is called recursion. I hope you know the difference between a function definition and function call in a program. Constructing a recursive function is not a big thing. Look at the following program.

def function():
    print("Function Called") # Statement 1
    function()               # Statement 2function()                   # First Function Call

The function function() is an example for recursive function. But we have to check whether this will work or not. Consider the defined function in the previous program. The function is called in the main function. We know that whenever a function is called, the statements written inside the function will be executed. The first function call is mentioned in the program.

After the function is called, the very first statement to be executed is the print(“Function Called”) . Then the second statement is function() which means we are calling the same function again. I hope you can understand one thing. This function also has another function call inside the definition. This process will happen continuously without any interruption. That means the loop is not going to stop anywhere. The chance of getting ended with an infinite loop is high in recursion. That is the one thing a programmer must care about. Let me explain how to write a recursive function without any error.

Steps in writing recursion function

The proper recursive function can be achieve with three steps. The steps are given below.

• Finding the base case
• Finding sub problem argument
• Function definition

Let me explain the steps with the help of traditional recursion based problem factorial of a number. The factorial of a particular number n can be obtained by multiplying the numbers from 1 to n. The mathematical definition is written below.

n! = 1 x 2 x 3 x …. x n-1 x n

The major thing in recursive function is the ability to split the problem into sub problem. The same definition can be written in the following format.

n! = ( 1 x 2 x 3 x …. x (n-2) x (n-1)) x n = (n-1)! x n

For example, 5 ! = 5 x 4 x 3 x 2 x 1 = 5 x 4! = 5 x 4 x 3! . This kind of problems can be solved using recursion. The factorial of any number can be determined by multiplying the number with the factorial of its previous number.

Finding Base Case for Factorial Program

The base case the value in which the recursion needs to be stopped. In the factorial problem, the sub problem is calculated for n-1 . If the value of n is 1 then the n-1 will be 0. By defining the value of 0! inside the program, the recursion will get a stop when it meets the base case. So the program must be stopped at the condition n<=0 .

Finding sub problem argument for Factorial Program

In the recursive call, the argument must be passed in a certain way that alters the value of the n continuously. In the factorial program, the sub problem is created using n-1 . So that the argument must be passed inside the recursive call is (n-1).

Function Definition for Factorial Program

The function definition is the process of deciding where the function to be called. We already discussed the base case of the program. So that the function can be called except the base case. For this, we can use simple if-else conditional structure. The complete program to find the factorial of a program is given below.

def factorial(n):
    if(n<=1):                 # Base Case
        return 1
    else:
        return n*factorial(n-1) # Recursive Call n = int(input("Enter a Number:"))
fact = factorial(n)
print("Factorial of",n,"is",fact)

Output

Enter a Number:5
Factorial of 5 is 120

Types of Recursive Function

Based on the no of recursive calls in a function the recursion can be classified into three types. The classification is given below.

• Linear Recursion
• Binary Recursion
• Multiple Recursion

Implementation of Recursion in Various Problems

Let us do some practical implementation of recursion in the following problems. Each problem is implemented in normal way as well as recursive way.

• Fibonacci Series
• Sum of elements in list
• Binary Search

Fibonacci Series

Fibonacci series is a mathematical sequence of numbers obtained by adding two preceding numbers in the sequence. The first number in the series is 1. As there is no preceding number for this, we can add zero to the first number to get the second number. 1 + 0 gives 1. Now to get the third value you can add first and second value. Let us try to get the value at the position n using two different approaches.

n = int(input("Enter the position:"))
a=0
b=1
for x in range(n-1):
    temp = a + b
    a = b
    b = temp
print(temp)

This method is used to trace the value by step by step using for loop. We can do this in recursive way. The base condition is n<=1 and the arguments are two preceding positions of n. So that the arguments will be n-1 and n-2.

def fib(n):
    if(n<=0):
        print("Enter Correct Value")
    elif(n==1 or n==2):
        return 1
    else:
        return fib(n-1)+fib(n-2)
n = int(input("Enter a Number:"))
print(fib(n))

Output

Enter a Number:9
34

The Fibonacci series solved using recursion is an example of binary recursion.

Sum of elements in a list

Sum of elements is calculated by adding the elements in all indexes in a list. The sum of elements can be solved in many ways. Here, I written two logical implementations using for loop and recursion.

my_list = [1, 2, 3, 4, 5]
temp = 0
for x in my_list:
    temp = temp + x
print(temp)

Using recursion

def add(list,size):
    if(size==0):
        return 0
    else:
        return list[size-1] + add(list,size-1)my_list = [1,2,3,4,5]
print(add(my_list, len(my_list)))

Output

This type of recursion is a linear recursion.

Binary Search

Binary search is an algorithm used to find the position of a particular element in a list. But one thing must be noted before executing binary search. The binary search will work only on the list that sorted already. In binary search we have to compare the value to the middle element of the list. If the middle element is greater than the passed value then there is no use in searching the second half of the list. This is the concept of binary search.

my_list = [1, 2, 3, 4, 5]
x = 3
start = 0
end = len(my_list)-1
mid = 0while start<=end:
    mid = (start + end)//2
    if(my_list[mid]<x):
        low = mid+1
    elif(my_list[mid]>x):
        high = mid -1
    else:
        print(mid)
        break

Binary search using recursion

def bin(list,x,start,end):
    mid = (start + end)//2
    if(list[mid]==x):
        return mid
    elif(list[mid]>x):
        return bin(list,x,start,mid-1)
    else:
        return bin(list,x,mid+1,end)my_list = [1, 2, 3, 4, 5]
x = 3
start = 0
end = len(my_list)-1
mid = 0print(bin(my_list,x,start,end))

Output