Monday, March 23, 2020

Python Recursion


Recursion is a well-known concept in programming languages. In Recursion a function calls itself to be invoked again before the original function call terminates. We can consider the factorial operation that is used to calculate the factorial of a given integer. Factorial can be defined for all non-negative integers. To calculate the factorial we need to apply the following operations,

  • If the input number is 0, then the value is 1.
  • Otherwise, the value of factorial is that number times the factorial of one less than the input number.

Simple, implementation of the factorial program can be described as follows:

def factorial(num):
    if num == 0:
        return 1    else:
        return num * factorial(num - 1)

The evaluation is performed as,

We can also have parallel recursive function calls, for example, the Fibonacci series. In a Fibonacci sequence, a. element is the sum of two previous elements. The first two elements are 0 and 1. We can write a recursive program to find a Fibonacci number as,

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

The calculation is performed as,

Fibonacci recursion java

The Tail call

A recursive function call that is the last operation to be performed before returning a value is known as a tail call. More specifically, return fun(n - 1)is considered as tail call, but return fun(n - 1)+ 1 is not a tail call because the addition is the last operation to be performed. 

The Tail Call Optimization and Tail Call Elimination

We can automatically reduce the recursion in recursive functions with the Tail call optimization(TCO). Another type of Tail call optimization is Tail call elimination (TCE), in which the reduction of a tail call to expression is performed that can be evaluated without recursion. 

There are many reasons to use Tail call optimization, like Low memory requirement and the interpreter can reduce the number of stack frame switches. However, Python has no form of Tail Call Optimization implemented inherently due to many reasons. So, other techniques are needed to curve this limitation. We can choose an appropriate method according to the use-case. We can define factorial and fib relatively easily to be performed in an iterative manner as the following code,

def factorial(n):
    product = 1    while n > 1:
        product *=n        n -= 1    return product


def fib(n):
    a,b = 0, 1    while n > 0:
        a,b =b,a + b
        n -= 1    return a

This is the best technique to remove recursion, but this is very difficult to implement in large functions. The second tool is lru_cache decorator that is used to reduce the number of redundant calculations.

When should we use recursion?

The answer is “only a few times”, because, all of the recursive methods can be coded in an iterative manner too. We simply need to figure out how to do so.

However, there are very few cases where recursion is working fine. For example, we can use recursion in Python when the expected inputs wouldn't result in a significant number of recursive function calls. A recursion is a powerful tool in functional languages like Haskell or Scheme.