Recursion

Introduction

"In order to understand recursion, one must first understand recursion."

• 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 recursive function must include a termination condition.

Examples

Example 1
This 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. Keep in mind that it is not a function call restarting itself; it is hundreds of function calls that are each unfinished.

#include <stdio.h>

void recurse ( int count ) /* Each call gets its own copy of count */
{
    printf( "%d\n", count );
    /* It is not necessary to increment count since each function's
       variables are separate (so each count will be initialized one greater)
     */
    getchar();
    recurse ( count + 1 );

}

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

  return 0;
}

Example 2
To halt a series of recursive calls, a recursive function will have a condition that controls when the function will finally stop calling itself.

#include <stdio.h>
 
void count_to_ten ( int count )
{
    //we only keep counting if we have a value less than ten
       if ( count < 10 )   
       {
            printf("%d",count);
            getchar();
           count_to_ten( count + 1 );
       }
}
int main()
{
  count_to_ten ( 0 ); 
}

Example 3: Fibonacci numbers

int Fibonacci(int nNumber)
{
    if (nNumber == 0)
        return 0;
    if (nNumber == 1)
        return 1;
    return Fibonacci(nNumber-1) + Fibonacci(nNumber-2);
}
 
// And a main program to display the first 13 Fibonacci numbers
int main(void)
{
    using namespace std;
    for (int iii=0; iii < 13; iii++)
        cout << Fibonacci(iii) << " ";
 
    return 0;
}