Applications of the recursive computing paradigm

Recursion is a computing technique that helps solve complex problems in a simple way, by using the result of the previous value of that function and finding a relation between the previous result, current result and the current value. The result we use would have been obtained using the answer for previous value, and the cycle would go on till we would reach a value for which we know the answer. This value, also referred to as the ‘base case’ would give us the answer to all the other cases, known as the ‘recursive cases’.

 For example, let us calculate the result of n! (Factorial of a number n) using recursion. In recursion, we  will use the value of n-1!, and multiply number n to it. To obtain the value of n-1!, it would use the value of factorial of n-2, and so forth. This continues till it reaches a value for which we know the answer. In this example, we know that the value of 1! is 1. Thus we would keep reducing the problem from n to n-1 to n-2…to 1, for which we know the answer. We would use this answer to find values of all unknown successive values. So we multiply 2 to 1! to get the factorial of 2 and we keep multiplying successive numbers to get the value of their factorials. The basic idea of recursion is to reduce a problem, and take it to the step for which we know the value.

Recursion is very useful in solving complicated problems, such as the traditional problem ‘towers of hanoi’.In this problem, we are given n number of disks, and our job is to transport the disks from tower A to tower C (as shown in the figure). However, we can only move one disk at a time, and also we cannot place a bigger disk on a smaller disk.

Picture Source: http://www.alper.net/wp-content/uploads/2008/03/hanoi.jpg

The problem is very complicated to solve with iteration. However, it is a small and comparatively easy to understand problem with the recursive approach. Here is the approach-

a)    Consider it is solved for n-1 disks, and we can move n-1 disks at our disposal.
b)    So, we move n-1 disks to tower B.
c)    Then we move disk n to tower C.
d)    Now, we can move the n-1 disks to tower C, over disk n, and the problem is solved.
e)    The problem for n-1 disks would have been solved by using the same procedure replacing n by n-1 and n-1 by n-2. We would keep reducing the problem, till we reach a value for which we know the answer. In this case, we know that for n=1, we move the disk 1 directly to Tower C.

Thus in recursion, we just need to find a relation that gives us the answer for ‘n’ and we believe that we know the answer for n-1. Though, in reality we do not know the answer to n-1. But we find that out by finding out the answer for n-2, n-3 and so forth till we reach a given value for which we know the answer. Hence, recursion makes problem solving easy compared to other approaches.

However, the disadvantage of recursion shows when it comes to computing. Recursion is a slower and more space taking process than iteration, thus making its efficiency lesser than iteration for the same algorithm. Recursion requires more space as it stores the values to be calculated in ‘stacks’. It is slower as function calls take time compared to calculations within the same function. To understand this, we can compare the computer to our brain. For example, if we were given a problem to add all numbers from 1 to 5. The iterative way would require us to add 1, and then add 2 to it, and result in us just adding just all numbers from 1 to 5 without thinking anything. However, a recursive approach would require us to start from 5, and add to it the sum of numbers from 1 to 4. This would require us to keep 5 in our brain and find the sum of numbers 1 to 4. This in turn would require us to keep 4 in our brain and solve for all numbers from 1 to 3, and repeat the cycle till we reach the base case, which is adding all numbers from 1 to 1, which we know is 1. So, recursion would require us to keep numbers from 2 to 5 in our brain which requires additional space. Also, it makes calculation slower than the iterative procedure, as we can see that it is more complicated for us to try and call the ‘function’ again and again, rather than simply adding the consecutive numbers as a part of the same function.
But we cannot forget the importance of recursion in daily life in solving complicated problems. Problems such as the towers of Hanoi are made so much simpler by using recursion! Also, recursion at times has solutions to problems which are faster than their iterative equivalents. For example, quick sort, an application of recursion is one of the fastest sorting techniques used in modern world!