Recursion: Recursion is the process of solving a problem by reducing it to smaller versions of itself. In mathematics, we all have learned how to calculate the factorial of a non-negative integer. For example, the factorial of 5, written as 5! is given by 5!=5xd4x3x2x1=120. Similarly, 4!=4x3x2x1=24, 3!=3x2x1=6, and soon. Also, factorial of 0 is defined as 0!=1. Now, observe that 5!=5x4x3x2x1=5x(4x3x2x1)= 5x4!, Similarly, 4!=4x3!, 3!=3x2!, and so on. In general, if n is a non-negative integer, then the factorial of n, written as n! can be defined as follows: 1 ifn=0....... | n= nx(n-1)! ifn>0 ....... ll By this definition, if n>O, we first find (n-1)! and then multiply it by n. To find (n-1)!, we apply the same definition again. That is, If (n-1)>0, we find (n-2)!, and then multiply it by (n-1). This process is repeated till the time the value of n becomes 0, which is then given by eqauation-!. Let us apply this definition to find 3!. Here n=3. Because 3>0, therefore by equation-ll, 3!= 3x2!. Next, for 2!, again 2>0, so by equation-ll, 2!=2x1!. And, for 1!, again 1>0, so by equation-ll, 1!=1x0!. Finally, for O!, since n=0, therefore we use equation -l, which directly gives 0! as 1. Now, substituting 0! into 1! gives 1!=1x0!=1x1=1. This gives 2!=2x1!=2x1=2, which in turn gives 3! =3x2!=3x2=6.The factorial calculation in above example illustrates the essence of the way recursion works. To obtain the answer to a large problem, a general method is used that reduces the large problem to one or more problems of a similar nature but a smaller size. The same general method is then used for these subproblems, and so recursion continues until the size of the subproblems is reduced ta some smallest, base case, where the solution is given directly without using further recursion. In other words, every recursive process consists of two parts: 1. A smallest, base case that is processed directly without recursion, and 2. A general method that reduces a particular case to one or more of the smaller cases, thereby making progress toward eventually reducing the problem all the way to the base case. In the above factorial example, equation-I is the base case and equation-ll is the general case. In computer science also, the concept of recursion works in a similar way. Here, we talk about recursive algorithms and recursive functions. An algorithm that finds the solution to a given problem by reducing the problem to smaller versions of itself is called a recursive algorithm. The recursive algorithm must have one or more base cases, and the general solution must eventually be reduced to a base case. A function that calls itself is called a recursive function. That is, the body of the recursive functioncontains a statement that causes the same function to execute again before completing the current call. Recursive algorithms are implemented using recursive functions. In the tapic on “applications of a stack", we learned that all the active (called but not completed) functions are kept on a stack. That is, each time a function is called, a new frame describing its context is pushed onto the stack. In regard to stack frames for function calls, recursion is no different from any other function call. That is, as far as the internal stack implementation of function calls is concerned, it makes no difference whether the context frames pushed on the stack come from different functions or from repeated occurrences of the same function. For the above factorial example, a C++ recursive function is defined below. int factorial(int num) { if(num ==0) { return 1; } else { return num+factorial(num-1); } } Where ‘num’ is a non-negative integer number whose factorial is to be calculated. It may be noted that for every recursive function, there always exists an iterative version as well. For the above factorial example, a C++ iterative function is defined below.int factorial(int num) { if(num==0) { return 1; } int fact=1; for(int i=num;i>=1;i--) { fact=fact*i; } return fact; } However, the converse is not always true, i.e., every iterative function may or may not have a corresponding recursive version.