23.Recursion

Recursion is a method of solving problems that involves breaking a problem down into smaller and smaller sub problems until you get to a small enough problem so that it can be solved trivially. Usually recursion involves a function calling itself. While it may not seem like much on the surface, recursion allows us to write elegant solutions to problems that may otherwise be very difficult to program.

Recursion is the process of defining something in terms of itself.It is legal for one function to call another, and you have seen several examples of that. It is also legal for a function to call itself. It may not be obvious why that is a good thing, but it turns out to be one of the most magical and interesting things a program can do.

For example, look at the following function:
def countdown(n):
    if n == 0:
        print("Blastoff!")
    else:
        print(n)
        countdown(n-1)
A call to this function countdown(5) will print
5
4
3
2
1
Blastoff!

Advantages of recursion
Recursive functions make the code look clean and elegant.
A complex task can be broken down into simpler sub-problems using recursion.
Sequence generation is easier with recursion than using some nested iteration.

Disadvantages of recursion
Sometimes the logic behind recursion is hard to follow through.
Recursive calls are expensive (inefficient) as they take up a lot of memory and time.
Recursive functions are hard to debug.

Infinite recursion

If a recursion never reaches a base case, it goes on making recursive calls forever,and the program never terminates. This is known as infinite recursion, and it is generally not considered a good idea. Here is a minimal program with an infinite recursion:

def recurse():
    recurse()

In most programming environments, a program with infinite recursion does not really run forever. Python reports an error message when the maximum recursion depth is reached.By default, the maximum depth of recursion is 1000. If the limit is crossed, it results in RecursionError.

Following is an example of a recursive function to find the factorial of an integer.

Factorial of a number is the product of all the integers from 1 to that number. 

For example, the factorial of 6 (denoted as 6!) is 1*2*3*4*5*6 = 720.
Example of a recursive function
def factorial(x): 

     """This is a recursive function to find the factorial of an integer""" 

     if     x ==0: 

         return 1 

     else: 

         return (x * factorial(x-1)) 

 num = 3 

print("The factorial of", num, "is", factorial(num))

Output

The factorial of 3 is 6

In the above example, factorial() is a recursive function as it calls itself.

When we call this function with a positive integer, it will recursively call itself by decreasing the number.
Each function multiplies the number with the factorial of the number below it until it is equal to one. This recursive call can be explained in the following steps.

factorial(3)                # 1st call with 3 

3 * factorial(2)          # 2nd call with 2 

3 * 2 * factorial(1)    # 3rd call with 1 

3 * 2 * 1*factorial(0)# 4th call with 0

3 * 2 * 1 * 1              # return from 4th call  when x=0

3 * 2 * 1                    # return from 3rd call  

3 * 2                          # return from 2nd call 

6                                 # return from 1st call

Recursion ends when the number reduces to 0. This is called the base condition.Every recursive function must have a base condition that stops the recursion or else the function calls itself infinitely.

Example Programs