How to use Recursion / Recursive Functions in C++ with Example or Exercise

Online Tutorial : How to use Recursion and  Recursive Functions in C++ programming languages with Example  Code or Exercise 

RECURSION

               Recursion is a very powerful tool that simplifies the job of the programmer. The idea is to define a problem in terms of a simpler version of itself. Thus the problem is being reduced into a simpler version which then defines it in an even simpler way. The process is repeated until we get a trivial case, which has been already defined in the problem. Such an approach is called recursive approach and such an algorithm is termed as recursive algorithm.

How to Calculate Factorial Recursively?

               Factorial is an important mathematical function and factorial of any nonnegative integer 'n' is defined as the product of all the integers from 1 to n. Factorial of 0 and 1 are defined to be 1. By this definition factorial of 4 and 5 will be:

Fact(4) = 4*3*2*1 =24 Fact(5) = 5*4*3*2*1 =120

               An iterative algorithm to solve the problem can be using a for loop as follows: i) Initialize product to 1. ii) For var from 1 to n product = product * var End For iii) product gives the factorial of n.
               Now if we look at the problem again, we can make a strange observation that Fact(5) is actually 5 multiplied with Fact(4). Now lets go back to the definition of factorial: Fact(n) = n*(n-1)*(n-2)*….*1 Fact(n-1) = (n-1)*(n-2)*….*1
               So we can make a generalization that Fact(n) is actually n multiplied by Fact(n-1). Remember that a definition that defines a problem as a simple form of it, is called a recursive definition. But "How far this simplification can go?" is the question. Given an 'n', we will be defining its factorial in terms of Fact(n-1), which can further be defined in terms of Fact(n-2) and so on. We will repeat the process until we reach Fact(0). Should we define it as 0*Fact(-1)? But remember we don't need to do so because Factorial is not defined for negative integers and because we already have the information that Fact(0) is 1. So that's the trivial case we are looking for. Every recursive algorithm has such a trivial case. A recursive algorithm of the factorial problem can be given as:

Fact(n) { if n is 0 answer is 1 else answer is n* Fact(n-1) }

               Note the simplicity and beauty of a recursive definition. However, it should be noted that in such a simple problem, a recursive algorithm might not be an efficient one. Calling of the function repeatedly is what makes the algorithm an inefficient one. The comparison of recursive and iterative technique is made in the next section.

Are Recursive Algos better than Iterative ones?

               It is not necessary that the recursive algorithm is better than the iterative one because there are many cases in which the iterative solution is better. The most prominent example is that of the factorial problem. The iterative solution is so much simpler than the recursive one that one might think that why to use the recursive one. But, this might not be the case in other problems. So, it is better to keep the options open and think before jumping to any conclusion about whether to use a recursive algorithm or an iterative one.

How to Calculate Greatest Common Divisor(GCD) Recursively?

               Well if I ask you what was the first recursive algorithm you used to solve a problem, very few of you will give a correct answer. This is because most of us don't realize that the method we used to calculate GCD of two numbers in Grade IV, was a recursive one. Let us have a revision of the GCD problem.
               We are given two integers x and y and we have to calculate GCD of the two. Our method is that we divide the larger integer by the smaller one. If the remainder is zero, we declare that the smaller integer is the GCD. If the remainder is nonzero, we repeat the same procedure with the remainder and the smaller integer i.e. we will try to find GCD of the remainder and the smallest number. The above recursive algorithm is given below in psuedocode:

If x<y then { GCD(x,y) is GCD(y,x) } Else { If x%y = = 0 then GCD(x,y) is y Else GCD(x,y) is GCD(y,x%y) }

Now it shouldn't be a problem to implement the above algorithm in C++ or any other language. Try to think about an iterative version of finding GCD of two numbers. This will give you an idea of the benefit that recursive algorithms provide.

COMMON PROGRAMMING ERRORS IN RECURSION

               During recursion, the following programming Errors may be faced:

Stopping Condition for Recursive Functions:

               The most common problem with a recursive problem is that a Recursive problem involves the specification of a stopping condition. If this condition is not correct, then the function may call itself indefinitely or until all memory is used up. Normally a "stack overflow" run time error is generated, indicating that the recursive program is not terminating. Thus you have to make sure that all the stopping cases be identified and correct condition is provided for each one. Also make sure that each recursive steps moves closer to the stopping condition not away from it. Make certain that repeated recursive calls eventually lead to a stopping case.

Missing Return Statements:

               It is very essential that every path through a function that returns a value lead to a return statement. When multiple returns are there in a function sometimes easily one return statement may be omitted creating problems. Such an omission will go unnoticed by the compiler and you wont get the correct result.

A Few Optimizations for Recursive Functions:

• The recopying of large arrays or other large data structures inside a recursive function can easily consume large amount of memory. Such copying should always be done when only essential (sometimes it is necessary for data protection). If this is the case even then effort should be made to make an iterative program which manipulates this large amount of data and passes it to the recursive function when required.
• It is a good idea to introduce an iterative function to handle preliminaries of a recursive function call when error checking is involved.
• It is sometimes difficult to observe the result of a recursive function's execution. If each recursive call generates a large number of output lines and there are many recursive calls the output will scroll down more quickly the screen than it can be observed. This can be avoided by using getch () or any other programming technique.

How to solve the "TOWERS OF HANOI" Problem Using Recursion?

               You have been using recursive definitions to solve a problem and it is not a very difficult task. Now the real part is that we are given a problem and we find a recursive algorithm ourselves. This is somewhat more difficult and it comes with practice. "Towers of Hanoi" problem is a classical problem and we are to find a recursive algorithm to solve the problem. Let us have a look at the problem.
               We have three pegs A, B, and C. 'n' disks are placed on the peg A such that a larger disk is always below a smaller one. The objective is to move the 'n' disks from the peg A to the peg C using the peg B as auxiliary. Some restrictions are that only one disk can be moved at a time, that only the top disk may be removed from a peg and that a larger disk may never be placed on a smaller one.
               Think about the problem and try to represent it as a similar but simpler problem. The algorithm will not be given in the handout but it will be discussed in the lecture.

 

 

EXERCISES

• Write an iterative program to calculate the factorial of any number.
• Write a recursive program to calculate the factorial of any number.
• Fibonacci numbers provide an interesting example of recursion. Fibonacci of 0 is defined to be 0 and that of 1 is 1. For any other nonnegative integer n, Fibonacci of n is the product of Fibonacci of n-1 and Fibonacci of n-2. Write a recursive program for Fibonacci of a number input by the user.
• Write a recursive program to calculate the GCD of any two integers.
• Write a recursive program, which gives the reversal of any string you might have entered. Say, if the input was "pqrst" the output will be "tsrqp".
• Write a recursive program to solve the problem of Towers of Hanoi.
• If we take:
                 C (n, r) = n! /r! (n-r)!
           Then write a recursive program to calculate C (n, r)