Recursive Functions 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.

• base case, in which the problem is simple enough to solved directly without making any 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 bit with sub-parts of the problem obtained in the first step. Third, the result is obtained by combining the solution of simpler sub-parts.

Thus, we see that recursion utilized divide and conquer technique of problem solving. 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. Therefore 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.

To understand recursive functions, let us take an example of calculating factorial of a number. To calculate n! what we have to do is multiply the number with factorial of number that is 1 less than that number. In other words, n! = n * (n – 1) !

Let’s say that we need to find the value of 5!

5! = 5 * 4 * 3 * 2 * 1

This can be written as

5! = 5 * 4! where 4! = 4 * 3!

Therefore

5! = 5 * 4 * 3!

Similarly we can also write

5! = 5 * 4 * 3 * 2!

Expanding further

5! = 5 * 4 * 3 * 2 * 1!

and we know

1! = 1

Now, if you look at the problem carefully, you can see that we can write a recursive function to calculate the factorial of a number.

So the Base case is when n= 1 because if n=1 the result is known to be 1 as 1! = 1. And the recursive case of the factorial function will call itself but with smaller value of n, this can be given as.

factorial = n * factorial(n-1)

Let’s write the factorial of a number recursively.

def fact(n):
    # base case
    if (n==1 or n==0):
        return 1
    else:
        # recursive case
        return n * fact(n -1)

n = int(input("Enter the value of n: "))
print("The factorial of", n, "is", fact(n))

#output
Enter the value of n: 5
The factorial of 5 is 120

Note – The base case of a recursive function acts as the terminating condition. So, in the absence of an explicitly defined base case, a recursive function would call itself indefinitely.

Let’s look at another example of recursive function.

The Fibonacci series can be written as

0  1  1  2  3  5  8  13  21  34  55...

That is the third term of the series is the sum of the first and second terms. On similar grounds, fourth term is the sum of second and third terms, so on and so forth.

Now let’s write a recursive function to solve the Fibonacci Series.

def fibonacci(n):
    # base case
    if n < 2:
        return 1
    # recursive case
    return fibonacci(n - 1) + fibonacci(n - 2)

n = int(input('Enter the number of terms: '))
for i in range(n):
    print('Fibonacci(', i, ") = ", fibonacci(i))

#output
Enter the number of terms: 8
Fibonacci( 0 ) =  1
Fibonacci( 1 ) =  1
Fibonacci( 2 ) =  2
Fibonacci( 3 ) =  3
Fibonacci( 4 ) =  5
Fibonacci( 5 ) =  8
Fibonacci( 6 ) =  13
Fibonacci( 7 ) =  21