Programming with C/C++ Language
Recursion in C++

1. Recursion in C++

Recursion is the process of repeating application of an algorithm.

Recursion technique expresses operations in terms of themselves. In C++, this takes the form of a function that calls itself.

In recursive functions, the instructions is to repeat the process; that makes it similar to a loop because it repeats the same code.

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.

2. Examples

2.1. A simple example

void recursive()
{
  recursive(); // The function calls itself
}

int main()
{
  recursive(); // Sets off the recursion
} 
 

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.

Here is a code that shows how many times the function is called before the program terminates:

 
#include 

using namespace std;

void recursive (int count ) 
// Each call is counted 
{
  cout<< count <<"\n"; 
  // each count will be initialized one greater
  recurse ( count + 1 );
}

int main()
{
  recurse ( 1 ); 
  // First function call, so it starts at one        
} 

This simple program will show the number of times the recurse function has been called by initializing each individual function call's count variable one greater than it was previous by passing in count + 1.

2.2. A factorial function

Here is two ways to calculate the fatorial. Recursive method and iterative method.

int recur_factorial (int n){
	if (n==0) 
	{
	return 1;
	} else {
return n * recur_factorial (n-1);
}
}

--------------------- 

int  iterat_factorial(int n) 
  {
      int f = 1;
      int i;
      for(i = 1; i <= n; i++) 
      {
      f *= i;
      }
      return f;
  } 
 

2.3. The Fibonacci sequence

//   Fibonacci in C++ 
 
Recursive: 
---------- 
 
long rec_fib(long n) {
    if (n <= 1) return n;
    else return rec_fib(n-1) + rec_fib(n-2);
}
 
Iterative:
---------- 

long iterat_fib(long n) { 

    if ((n == 1) || (n == 2)) {
        return 1;
    } else {
        long prev = 1, current = 1, next = 0;
        for (long i = 3; i <= n; i++) {
            next = prev + current;
            prev = current;
            current = next;
        }
        return next;
    } 
	
	}

3. The Fibonacci program

 
#include 

using namespace std;

// ----------Recursive: ----------------

long recu_fibonacci(long n) {
    if (n <= 1) return n;
    else
    return recu_fibonacci(n-1) + recu_fibonacci(n-2);
}

//-------- Iterative: ----------------

long iter_fibonacci(long n) {

    if ((n == 1) || (n == 2)) {
        return 1;
    } else {
        long prev = 1, current = 1, next = 0;
        for (long i = 3; i <= n; i++) {
            next = prev + current;
            prev = current;
            current = next;
        }
        return next;
    }
	}

int main() {

    char choice ;
	int number;

	cout << "\n\t Enter a positive integer 
	less that 50 : --> ";
	cin >> number;
	if (number < 0 || number > 50)
		cout << "\n\t That is not a 
		positive integer less than 50 ..\n";
	else
	{
    cout << "\n\t Enter r for recursive or 
	i for iterative : --> ";
	cin >> choice;

	if (choice == 'r'){
	cout << "\n\t fibonacci of " << number << " is :  "
	<< recu_fibonacci(number) << endl;
	}

	else if (choice == 'i'){
    cout << "\n\t fibonacci of " << number << " is :  " 
	<< iter_fibonacci(number) << endl;
	}

	else
	{
	cout << "\n\t specifiy a choice " << endl;
	}
	}
    cout << "\n\n"  << endl;

    return 0;
}

Using CodeBlocs: