Tuesday, 13 December 2016

Python Recursion or Recursive Function

Python Recursion or Recursive Function - We have been exploring Python functions and we have covered Python function basics, Keyword & optional arguments, function return values and variable length arguments, so far. Now, we start our discussion on types of function, there are two of them - Recursive function and Iterative function. In this article, we will be studying the former one - Recursive function or Recursion.

python-recursion-recursive-function

In any program, when a function calls itself, we call it Recursive function or Recursion. We can put this statement in syntactical form as below:

def myFunction( params ):
    ...
    ...
    ...
    myFunction( params )
    ...
    ...
    ...

In above syntax, we define a function, perform some operations and call the function again. At each step, the function calls itself recursively and performs some operations. So, this obeys the rule of recursion and can be called a Recursive function. Looking at this syntax, it might seem to be a never ending loop, it may not exit anytime soon. But, in a recursive function, at each step, the problem becomes smaller and simpler. So, with each recursive call, function calls itself with a smaller version of the main problem statement. At some point, the problem statement should converge at base case, where a value is returned and recursion stops. Thus, we can modify above syntax and put it as:

def myFunction( params ):

    # Base case
    if ( base_case_1 ):
        return <some_value>
    elif ( base_case_2 ):
        return <some_other_value>

    ...
    ...
    ...
    myFunction( params )
    ...
    ...
    ...

Things will be pretty clear when we see a couple of examples of recursion. The first and the most popular example is to calculate factorial of a number. A factorial of 'n' is nothing but the product of all non-zero positive integers less or equal to n. So, factorial(4) = 4*3*2*1 = 24. In this case, we can identify the base case first, which is factorial(1) = 1. So, as soon as n reaches '1', we return '1'.

factorial(4) = 4 * 3 * 2 * 1
             = 4 * (3!)
             = 4 * (3 * [2!])
             = 4 * 3 * [2 * 1!]

If you observe carefully, our main problem is getting disintegrated into small problem, at every step. At every step other than base case, we get n * (n-1)!, and our new problem is to solve (n-1)!. This way, we approach towards our base case n = 1, which we know is '1'.

>>> def factorial(n):
...     if n == 1:
...             return 1
...     return n * factorial(n-1)

We have implemented the same logic in above code. If n > 1, it returns n * factorial(n-1), which gives us factorial(n-1) - a new sub-problem to solve. Lets us modify the code a bit, to debug what exactly is happening inside.

Example 1: Factorial of a number using recursion

>>> def factorial(n):
...     print 'Calculating factorial(' + str(n) + ')...'
...     if n == 1:
...             return 1
...     result = n * factorial(n-1)
...     print 'Result of ' + str(n) + '* factorial(' + str(n-1) + ') = ' + str(result)
...     return result
...

Output:

>>> factorial(6)
Calculating factorial(6)...
Calculating factorial(5)...
Calculating factorial(4)...
Calculating factorial(3)...
Calculating factorial(2)...
Calculating factorial(1)...
Result of 2* factorial(1) = 2
Result of 3* factorial(2) = 6
Result of 4* factorial(3) = 24
Result of 5* factorial(4) = 120
Result of 6* factorial(5) = 720
720

In above output, we can easily see how our problem got decomposed till the base case, which then got us the final result returned. We now take a look at another example - Fibonacci series. In a Fibonacci series, each number is a sum of its two preceding numbers, first two numbers being 0 and 1. So, the series looks like 0, 1, 1, 2, 3, 5, 8, 13, 21, .... Normally, the problem statement is to find 'n'th term in the Fibonacci series.

Example 2: 'n'th term in Fibonacci sequence using recursion

Considering that our function name fib(n), we have two base cases as fib(0) = 0 and fib(1) = 1. If value of n does not match these base cases, we return the sum of n-1th term and n-2th term. It is clear that, if nth term in a Fibonacci series is fib(n), then n-1th term would be fib(n-1) and n-2th term would be fib(n-2). Thus, we return fib(n-1) + fib(n-2).

>>> def fib(n):
...     if n == 0:
...             return 0
...     elif n == 1:
...             return 1
...     return fib(n-1) + fib(n-2)
...

>>> fib(5)
5

>>> fib(6)
8

>>> fib(8)
21

Recursion has its own advantages and disadvantages. It takes less code to write recursive functions, thus less time. With recursion, a complex task is decomposed into simpler sub-tasks and code to perform simpler sub-tasks can be written and implemented for complex task. On the other hand, recursion is very hard to understand and debug. Recursive calls consume lot of memory, hence considered as expensive. An infinite recursive function may lead to system crash. So, it is very crucial to incorporate base cases in recursive functions.

With this, we end our discussion on Recursion. Please share your views and feedback on this article in the comment section below and stay tuned. Thank you.

0 comments:

Post a Comment