Python Recursion

• A function can call other functions. It is even possible for the functions to call itself. These types of construct are termed as recursive functions.

Recursion Concept:

Image Source: LinkedIn

---

We don’t think you are able to get the concept of recursion by seeing the previous image. Let’s try to understand the logic of recursion with the help of an example.

First, let’s understand the basic definition of recursion. When a function calls other different names function then this is a simple function calling but when the function call itself that is known as recursion.

You can see the below image for more clarification of normal function calling and recursion function calling.

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

n=int(input("Enter the value for Factorial: "))
result = factorial(n)
print("The factorial of given value is :",result)

Enter the value for Factorial: 4
The factorial of given value is  : 24

EXPLANATION:

In this code, to calculate factorial, we have defined a function factorial( ). A parameter ‘n’ is passed to the function which is nothing but the value whose factorial we want to find. We used the ‘ if ’ condition here. Whenever N =1, return 1. The function returns the value where we calculate factorial for N. In the above code, we took N=4. Let’s understand step by step what’s happening.

STEP 1: Here N is not equal to 1. So it returns N*factorial(N-1) i.e. 4*factorial(3).

STEP 2: Now the value for N=3. Again, N is not equal to 1. Hence, 3*factorial(2). Continue the procedure till N=1.

STEP 3: At the end, it will return the value of factorial(4). You can see the process of executing in the below image. i.e. 24

Advantages:

1. Makes code look clean and elegant.
2. A complex task can be broken down into simpler sub-problem using recursion.
3. Sequence generation is easier with recursion than using some nested iteration.

Disadvantages:

1. Sometimes the logic behind recursion is hard to follow through.
2. Recursive calls are expensive as they take up a lot of memory and time.
3. These codes are hard to debug.

Recursion Examples:

def fibonacci(n):
    if n == 0:
        return 0    
    if n == 1:
        return 1
    else:
        return (fibonacci(n-2) + fibonacci(n-1))

# N = int(input("Enter the input: ", ))
N = 8
print("Fibo Series: ",end="")
for i in range(0,N):
    print(fibonacci(i),end=" ")

Fibo Series:  0   1  1  2  3  5  8  13

def findFactorial(N):
    if(N==1):
        return 1
    return N*findFactorial(N-1)


# N = int(input("Enter the input: ", ))
N=6
factorialValue=findFactorial(N)
print("Factorial: ",factorialValue)

Factorial:  720

def Sum(N):
    if N==1:
        return(1)
    return (N+Sum(N-1))


n = int(input('Enter Input: '))
#n=5
addition = Sum(n)
print("Sum Of {} Natural Number Is: {}".format(n,addition))

Enter Input: 5
Sum Of 5 Natural Nmber Is: 15

def factors(x,i):
    if(x >= i):
        if ((x%i)==0):
            print(i)
        factors(x,i+1)

n=18
# n = int(input("Enter Integer Value: "))
factors(n,1)

1
2
3
6
9
18