Recursion

Recursion and Function Calls

Recursion

Looping can be accomplished by:
- while
- for
- do . . . while
Another way—recursion
a function calling itself
this is a form of repetition (looping)
infinite loop unless a stop condition is included in the algorithm (must have a terminating condition)
In mathematics we sometimes call these recurrence relations
Recursion is not unique to C++; many languages support it

Basic Idea

Figure out the pattern of repetition with calls to the recursive function
Find out what changes in the parameters to cause the problem to change with each recursive call
Figure out the base case or trivial case; this is what stops the recursion

More Recursion Details

A popular function that is defined recursively is the factorial function:

N! = N · (N - 1)!

This function assumes that N >= 1 and by definition 0! = 1. This function is recursive because it is defined in terms of itself. The traditional way of writing recursive definitions is like this:

0! = 1           	 base case 
N! = N · (N - 1)!	 recursive case

For example, 5! is defined like this:

5! = 5 · 4!

And 4! is defined like this:

4! = 4 · 3!

And so on:

3! = 3 · 2!
2! = 2 · 1!
1! = 1 · 0!
0! = 1		 this is the base case

Which ultimately gives us:

5 · 4 · 3 · 2 · 1 · 1 = 120

Another popular function that is defined recursively is the power function:

X^N = X · X^{(N - 1)}

This function assumes that N >= 2 and by definition X¹ = X. We would write the recursive definition like this:

X1 = X           base case 
X^N = X · X^{(N - 1)}  recursive case

Some terminology

Recursive call - A function call in which the function begin called is the same as the one making the call
Recursive definition - A definition in which something is defined in terms of smaller versions of itself
Base case - The case for which the solution can be stated non-recursively
General case (recursive case) - The case for which the solution is expressed in terms of a smaller version of itself
Recursive algorithm - A solution that is expressed in terms of (a) a base case and (b) a recursive case
Infinite recursion - The situation in which a function calls itself over and over endlessly
Tail recursion - A recursive algorithm in which no statements are executed after returning from the recursive call

Factorial Examples

The factorial function can be written non-recursively in C++:

int iterativeFact(int number)
{
  int factor = 1;
  int count;

  for (count = 2; count <= number; count++)
    factor = factor * count;

  return factor;
}

The factorial function can also be written recursively:

int recursiveFact(int number)
{
  if (number == 0)
    return 1;
  else
    return number * recursiveFact(number - 1);
}

Client code would call them in the normal fashion:


cout << iterativeFact(5) << endl;
cout << recursiveFact(5) << endl;

Output:
120
120

Tracing Function Calls

Given 3 functions as defined below:

int f1(int a, int b);
int f2(int x);
int f3(int x);

int f1(int a, int b)
{
  int x, y;

  x = f2(a);
  y = 4 + b;

  return x + y;
}

int f2(int x)
{
  int a, b, c;

  a = x;
  b = 5;
  c = f3(a + b);

  return c;
}

int f3(int x)
{
  int a;
  a = x * 3;     // snapshot taken before this executes

  return a;
}

What does the following program print?

void main(void)
{
  int x;
  float f;

  f = 2.7;
  x = f1(2, 3);

  cout << x << endl << f << endl;
}

This is a "snapshot" of what the runtime stack looks like just before the statement a = x + 3 is executed in f3:

Tracing Function Calls - 3

Given this definition of the factorial function fact:

int fact(int number)
{
  if (number == 0)
    return 1;
  else
    return number * fact(number - 1);
}

Trace the function calls of this program:

void main(void)
{
  int x;

  x = fact(4);
  
  cout << x << endl;
}

Given this definition of Print:

int Print(const int list, int first, int last)
{
  if (first <= last)
  {
    cout << list[first] << endl;
    Print(list, first + 1, last);
  }
}

Trace the function calls of from this statement:

  Print(list, 0, 2)

Tracing Function Calls - 4

void displayReverse(int charCount)
{
  char inchar;

  if (charCount == 1)
  {
    cin >> inchar;
    cout << inchar;
  }
  else if (charCount > 1)
  {
    cin >> inchar;
    displayReverse(charCount - 1);
    cout << inchar;
  }
}

This displayReverse function accepts input from the user. Assume that the user types:

ABC

after the program is started. The output from the program is

CBA

This is what a trace of the program looks like:

Back to Outline