In this post, we will be investigating the special function named as Recursion in Python.
Recursion is very powerful way to implement solutions to a certain class of problems. This class of problems is the one where the overall solution to a problem can be generated. Then, the overall result is generated by combining together the results obtained for the smaller problems.
A recursive solution in a programming language such as Python is one in which a function calls itself one or more times in order to solve a particular problem. In many cases the result of calling itself is combined with the functions current state to return a result.
In most cases the recursive call involves calling the function but with a smaller problem to solve. Alternatively, a function to generate a factorial number might call itself passing in a smaller number to process etc.
The key here is that an overall problem can be solved by breaking it down into smaller examples of the same problem. Functions that solve problems by calling themselves are referred to as recursive functions.
However, if such a function does not have a termination point then the function will go on calling itself to infinity. In most languages such a situation will result in an error being generated. Therefore it must have a termination condition.
Benefits of Recursion
However, the key benefit of recursion is that some algorithms are expressed far more elegantly and with less code when implemented recursively than when using an iterative approach. This means that the resulting code can be easier to write and easier to read.
These twin ideas are important both for the developers who initially create the software but also for those developers who must maintain software.
Recursion suits well to produce functional solutions to a problem. As a recursive function relies on its inputs and outputs and does not hold any hidden state.
Recursion in Python
Recursion in Python is perfectly legal to have a function that calls itself.
In Python we can write a recursive function such as:
def recursive_function(): print ('Calling recursive_function') recursive_function()
Here the function
recursive_function() is defined such that it prints out a message and then calls itself.
Of course, in the case of
recursive_function() this will result in infinite recursion as there is no termination condition. However, this will only become apparent at runtime when Python will eventually generate an error.
However, as earlier mentioned a recursive function should have a recursive part and a termination or base case part. The termination condition identifies when the base case applies. We should therefore add a condition to identify the termination scenario and what the base behavior is.
Disadvantages of Recursion
Although Recursion can be a very expressive way to define how a problem can be solved. It fails to be efficient as compared to the iteration. This is because a function call is more expensive for Python to process that a
In some languages, optimizations are possible to improve the performance of a recursive solution. One typical example relates to a type of recursion known as tail recursion. A tail recursive solution performs calculation before the recursive call. The result is then passed to the recursive step, which results in the last statement in the function just calling the recursive function.
In such situations the recursive solution can be expressed as an iterative problem. That is the programmer write the solution as a recursive algorithm but the interpreter or compiler converts it into an iterative solution. This allows programmers to benefit from the expensive nature of recursion while also benefiting from the performance of an iterative solution.