Recursive Function in Python

In Python, a recursive function is defined as a function that calls itself to solve a smaller version of its task until a final call is made, which does not require a call to itself. Every recursive solution has two major cases, which are as follows:

• the base case, in which the problem is simple enough to be solved directly without making further calls to the same function.
• Recursive case, in which first the problem at hand is divided into simpler sub-parts. Second, the function calls itself but with sub-parts of the problem obtained in the first step. Third, the result is obtained by combining the solutions of simpler sub-parts.

Thus, we see that recursion utilized a divide and conquer technique of problem-solving. The divide and conquer technique is a method of solving a given problem by dividing it into two or more smaller instances. Each of these smaller instances is recursively solved, and the solutions are combined to produce a solution for the original problem. Recursion is used for defining large and complex problems in terms of a smaller and more easily solvable problem. In a recursive function, a complicated problem is defined in terms of simpler problems, and the simplest problem is given explicitly.

Example a:

def fact(n):
    if(n<=1):
        return(1)
    else:
        return(n*fact(n-1))
number=int(input("Enter the value of number="))
Factorial=fact(number)
print("The factorial of ",number," is",Factorial)

Output:

Enter the value of number=5

The factorial of  5  is 120

Example b:

def GCD(x,y):
    rem=x%y
    if(rem==0):
        return(y)
    else:
        return(GCD(y,rem))
m=int(input("Enter the value of m="))
n=int(input("Enter the value of n="))
print("The GCD of ",m,"and",n," is",GCD(m,n))

Output:

Enter the value of m=8

Enter the value of n=4

The GCD of  8 and 4  is 4

Example c:

def fibonacci(n):
    if(n<2):
        return(1);
    else:
        return(fibonacci(n-1)+fibonacci(n-2))
m=int(input("Enter the value of m="))
for i in range(m):
    print("Fibonacci(",i,") = ",fibonacci(i))

Output:

Enter the value of m=6

Fibonacci( 0 ) =  1

Fibonacci( 1 ) =  1

Fibonacci( 2 ) =  2

Fibonacci( 3 ) =  3

Fibonacci( 4 ) =  5

Fibonacci( 5 ) =  8