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)

## 0 comments:

## Post a Comment