Data Structures and Algorithms Using Python

Recursion is a very important concept in programming technique. In programming there are situations where we may find that the solution of a problem can be achieved by solving smaller instances of that same problem. For example, in tree data structure, all the properties that comprise a tree also feature in its sub-trees. So, to get a solution for the tree first we need to get the solution of its sub-trees. Again to get the solution of a sub-tree we need to get the solution of the sub-trees of this sub-tree, and so on. This is the basis of recursion. This concept helps to solve many complex problems very easily.

6.1 Definition

In almost every programming language, a function or procedure may invoke other functions or procedures. Not only from other functions, a function may be invoked from within itself as well. When a function is invoked by itself, the function is called a recursive function. And the process is called recursion. Instead of direct invocation, it may happen that the first function invokes the second function and the second function again invokes the first function in turn. This is also recursion. So, we can define recursion as the process where a function is directly or indirectly invoked by itself. Though it is a comparatively more memory consuming process, it is very effective in implementation where the algorithm demands the same repetitive process but use of iteration is difficult.

For example, we can define factorial of n as n! = n * (n-1)!. So, to find the factorial of n we need to calculate factorial of n-1 first. Again, to calculate the factorial of n-1 we need to calculate factorial of n-2, and so on. But this process may not continue indefinitely. Stack will be overflowed in that case. Hence, we must impose some criteria based on which this invocation should be restricted. This is called base criteria or base condition. Thus, every recursive function must have a base condition. In the above example, we may set the base condition as: when the value of n is 0, instead of recursive call it directly returns 1.