Recursion or Recurse

From http://www.cprogramming.com/

“Recursion is a programming technique that allows the programmer to express operations in terms of themselves. In C++, this takes the form of a function that calls itself. A useful way to think of recursive functions is to imagine them as a process being performed where one of the instructions is to “repeat the process”. This makes it sound very similar to a loop because it repeats the same code, and in some ways it is similar to looping. On the other hand, recursion makes it easier to express ideas in which the result of the recursive call is necessary to complete the task. Of course, it must be possible for the “process” to sometimes be completed without the recursive call. One simple example is the idea of building a wall that is ten feet high; if I want to build a ten foot high wall, then I will first build a 9 foot high wall, and then add an extra foot of bricks. Conceptually, this is like saying the “build wall” function takes a height and if that height is greater than one, first calls itself to build a lower wall, and then adds one a foot of bricks.“

1 void recurse()
2 {
3 recurse(); //Function calls itself
4 }
5
6 int main()
7 {
8 recurse(); //Sets off the recursion
9 }

This program will not continue forever, however. The computer keeps function calls on a stack and once too many are called without ending, the program will crash. Why not write a program to see how many times the function is called before the program terminates?

01 #include
02
03 using namespace std;
04
05 void recurse ( int count ) // Each call gets its own count
06 {
07 cout<< count <<"\n";
08 // It is not necessary to increment count since each function's
09 //  variables are separate (so each count will be initialized one greater)
10 recurse ( count + 1 );
11 }
12
13 int main()
14 {
15 recurse ( 1 ); //First function call, so it starts at one
16 }

Recursively find the factorial of the smaller numbers first, i.e., it takes a number, finds the factorial of the previous number, and multiplies the number times that factorial…have fun. :-)

Use of recursion in an algorithm has both advantages and disadvantages. The main advantage is usually simplicity. The main disadvantage is often that the algorithm may require large amounts of memory if the depth of the recursion is very large.

Read more on Recursion:

  1. http://www.codeguru.com/cpp/cpp/algorithms/math/article.php/c15111
  2. http://www.cstutoringcenter.com/tutorials/cpp/cpp6.php
  3. http://en.wikipedia.org/wiki/Recursion

Leave a Reply

Your email address will not be published. Required fields are marked *