Recursion

Introduction

The literal meaning of recursion is the simultaneous use of a process directly or indirectly within the same process. Normally, a function in Python is called from the main program. But, sometimes, the users need to call a function from the body of the same function. This is done with the purpose that the code could be simple and clear. Hence, a function that calls itself (i.e., from its body) is known as Recursive function.

Recursion is an efficient technique to develop a function by using a minimum set of statements. It is designed such that the instructions within the function are repeatedly executed unless a given condition stands true. Hence, the user must be careful to implement the technique otherwise the logic will result in an infinite loop. You must keep in mind that all the problems can be solved without using recursive functions but by using recursive techniques many extra statements can be ignored. It allows your program to give the same result by occupying less space in memory for storage.

Recursive approach

In a recursive approach, the function keeps calling itself until the condition is met. Although, it is slower than iteration.

Every recursive function uses a condition to terminate. It is known as Base Case. As soon as the condition for base case is true, the control terminates the function otherwise, it keeps calling the function again and again. The statement that calls the function repeatedly from its block is said to be the Recursive Case

Advantages of Recursive functions

The recursive functions are advantages due to following reasons:

• Minimum number of variables are used to develop the logic.
• The recursive algorithm is precise, readable and efficient.
• Easier to debug and obtain error free results.

Disadvantages of Recursive functions

The disadvantages of recursive functions are as mentioned below:

• Recursive functions take more time during the execution than the iterative process.
• It may result in stack overflow, if the recursive call continues longer.

Types of Recursions

People describe the recursive function in many ways, but basically the recursive function can be categorized in the following two ways:

1. Direct Recursion

A function that is called from the body of the same function is said to be recursion or direct recursion. The direct recursion is further classified into the following three types:

1. Linear Recursion: Linear recursion is the most common way of creating a recursive function. In this system, the function call is included along with the processing statement. Calculating factorial of a number is the best example of linear recursion. Let us take a look how the factorial of a number can be calculated by using recursive technique.

def fact(n):
    if n==0:
        return 1
    else:
        return (n*fact(n-1))

#__main__
num=int(input("Enter a number:"))
f=fact(num)
print("The factorial of",num,"is",f)

Output :

Enter a number:5
The factorial of 5 is 120

2.Tail Recursion: Tail recursion is a type of linear recursion. It is slightly different from linear recursion in the fact that the method call is independent and is not included along with the processing statement. In this recursive structure, the function call statement is placed at the end of the function block. It executes all the statements of the function body before the recursive call.

# Display the numbers in descending order
def tail(n):
    if n==0:
        return
    else:
        print(n)
    tail(n-1) # tail recursion

# __main__
k=int(input("Enter a number:"))
print("Displaying numbers in decreasing order:")
tail(k)

Output :

Enter a number:5
Displaying numbers in decreasing order:
5
4
3
2
1

3.Binary Recursion: Normally, a recursive function is called from one point of the function block. But sometimes, it may happen that you need to call a function from multiple points of a function block. It is possible in Python programming. If a function is recursively called from two different points of its block, it is said to be a binary recursion. Finding nth Fibonacci element is the best example of binary recursion.

def fiboseries(num):
    if num==1:
        return 0
    elif num==2:
        return 1
    elif num>2:
        return fiboseries(num-1)+fiboseries(num-2)
    else:
        return -1

#__main__
n=int(input("Enter number of terms:"))
print("Fibonacci Series:")
for i in range(1,n+1):
    k=fiboseries(i)
    print(k)

Output :

Enter number of terms:12
Fibonacci Series:
0
1
1
2
3
5
8
13
21
34
55
89

2.Indirect Recursion or Mutual Recursion

Mutual recursion takes place when one method calls another method, which in turn calls the first method. This involves two or more methods which create a  circular calling sequence.

def even(n):
    if n==0:
        print(num,"is a Even Number")
    else:
        return odd(n-1)
def odd(n):
    if n==0:
        print(num,"is an Odd Number")
    else:
        return even(n-1)

#__main__
num=int(input("Enter a number:"))
even(num)

Output 1:

Enter a number:34
34 is a Even Number

Output 2:

Enter a number:55
55 is an Odd Number