Math 10 -- Notes N19

Notes N19

Math 10 -- D. C. Smolarski, S.J.
Santa Clara University, Department of Mathematics and Computer Science

[Return to Math 10 Homepage | Return to Notes Listing Page]

Preliminary
Recursion
Fibonacci Numbers Sample C++ Code
Reverse Example
void function Example
Comparison with Iteration
Other Recursive Examples

Preliminary: Background for Recursion

Remember back to procedure/function calls, and how they work. The standard rule for what happens at the invocation of a function is this: When a function (either void or returning a specific value) is called, control transfers from the point of invocation to the function code itself, and after the function's execution, control returns to where the function was called from! This is a simple enough rule, but it must be followed brutally without any exceptions!!

E.g.

	-----void Proc1()
	|    {
	|	...
	-----};
	-----void Proc2();
	|    {
	|	Proc1();	
	-----};
	-----int main() // Main Program 
	|    {  ...
	|	Proc2;
	|	// point "1"
	|	...
	-----}

NOTES:

Proc1 does NOT return to the Main Program because it was called from Proc2!! (Remember this application of the general rule given above and FOLLOW IT!!)
Proc2 does NOT return to the start of the Main Program but to the line after the place from which it was called, i.e., the line indicated by the comment point "1" above.

COMMENT: Up to now, the theory we have seen is applicable to many older programming languages (e.g., FORTRAN-77, BASIC). Now, we get to special features of newer languages (e.g., PL/I, Algol68, C, Ada, Pascal, C++, Fortran-90).

Recursion

Oftentimes some concepts, especially mathematical concepts, are defined in terms of themselves. Such definitions are called recursive definitions.

This is especially true for some number sequences.

EXAMPLE #1.

For example, the well-known Fibonacci sequence has the general formula

f_n = f_n-1+f_n-2 with the initial values of f₀ = f₁ = 1.

Thus, the sequence is: 1 1 2 3 5 8 13 21 ...

To find f₈, you need to know f₇ and f₆.

To find f₇, you need to know f₆ and f₅, etc.

REMEMBER that Fibonacci numbers are defined recursively (and is the most common example of recursion), but that recursion is a much bigger concept than Fibonacci numbers.

===> One important feature of C/C++ is that it allows functions to call themselves recursively.

NOTE: This feature was NOT available in earlier versions of FORTRAN and other older programming languages, but has been included in Fortran-90.

Recursion is NOT an easy concept to think about at first. Some have said that the human mind was not meant to think recursively. One has a sense of recursion if one has stood between two parallel mirrors, as in a hallway mirrored on both sides. In such a situation, one can see copies of oneself almost infinitely in both directions.

EXAMPLE #2.

Look at the sequence s_n defined by the following equation.

s_n = s_n-1 + s_n-2 + s_n-3

where s₀ = s₁ = s₂ = 1. This is sometimes called the "tri-bonacci sequence."

==> 1 1 1 3 5 9 17 ...

EXAMPLE #3.

t_n = 2t_n-1 - t_n-2

where t₀ = t₁ = 1.

==> 1 1 1 1 1 ...

EXAMPLE #4.

u_n = 3u_n-1 - u_n-2

where u₀ = 0 and u₁ = 1.

==> 0 1 3 8 21 ...

Fibonacci Numbers Sample C++ Code

It is relatively easy to transform a mathematical recursive equation into C/C++ code. Looking at the two statement definition of the fibonacci numbers (i.e., f₀ = f₁ = 1 [base case] and f_n = f_n-1+f_n-2 [general case]), we transform the code almost literally into C/C++ code using an if statement to test for the value of the subscript.

	#include<iostream.h>
	int fib(int n)
	{
	   if ((n == 1) || (n == 0)) //base cases
		return 1;
	   else
		return fib(n-1) + fib(n-2); //recursive case
	}
	int main()
	{
	   int num,out;
	   cin >> num;
	   out = fib(num);
	   cout << "f sub " << num << " is " << out<< endl;
	   return 0;
	}

As an example of how this code words, supposed we have the input value of 4, i.e., suppose that num receives an initial value of 4 in the main program.


fib(4) _____  fib(3) _____ fib(2) _____ fib(1) ______ 
{ELSE}	      {ELSE}       {ELSE} \     {THEN}
     \  	    \		    \		
       \	      \___ fib(1) _____ fib(0) ______
	 \		   {IF}		{IF}
	   \
              fib(2) _____ fib(1) ______
              {ELSE}       {IF}
		    \
		      \___ fib(0) ______
			   {IF}

Thus f₄ = _____

Reverse Example

This is another example of recursion that demonstrate the underlying principle behind the data structure called a "stack."

	#include<iostream.h>
	void StackTheCharacter()
	{
	   char TheCharacter;
	   cin.get(TheCharacter);
	   if (TheCharacter != '\n')
		StackTheCharacter();
	   cout << TheCharacter;
	}
	int main()
	{
	   cout << "Please enter a sentence." << endl;
	   StackTheCharacter();
	   cout << endl;
	}

Please enter a sentence.
HELLO
        H       E       L       L       O      \n
   get(TC) get(TC) get(TC) get(TC) get(TC) get(TC) 
   if      if      if      if      if      if
   cout    cout    cout    cout    cout    cout
        H       E       L       L       O       \n

OUTPUT:

`void function` Example

	#include<iostream.h>
	void p(int & a)
	{
	   int b;
	   b = a-1;
	   a = a-1;       |
	   if (a == 0)    |   main x
	      p(b);       |
	   a = b;         |
	}                 |   p(1st call)
	int main()        |        a           b
	{                 |
	   int x;         |
	   x = 1;         |   p(2nd call)
	   p(x);          |        a           b
	   cout << x << endl;
	}

OUTPUT ==>

Comparison with Iteration

Although for many people recursion is difficult to envision and even more difficult to trace, when given recursive mathematical formulas or problems that are more easily solved recursively than iteratively, a recursive implementation is usually significantly simpler than the corresponding iterative code. We note, however, that iterative code is often more efficient than recursive code!

As an example, let us rewrite the recursive code for computing a fibonacci number given above.

	#include<iostream.h>
	int fib(int n)
	{
	   int ________________________________________;
	   if ((n == 1) || (n == 0)) //base cases
		return 1;
	   else {

	   ___________________________________________

	   ___________________________________________

	   ___________________________________________

	   ___________________________________________

	   ___________________________________________

	   ___________________________________________

	   }
	}
	int main()
	{
	   int num,out;
	   cin >> num;
	   out = fib(num);
	   cout << "f sub " << num << " is " << out<< endl;
	   return 0;
	}

Other Recursive Examples

Look at the common definition of aⁿ. This is a shorthand for n copies of a multiplied together. In other words:

       aⁿ = a x a x a x a x a x ... x a
           |-------------n-------------|

But we can regroup the right side into a single a times n-1 a's as follows:

       aⁿ = a x (a x a x a x a x ... x a)
               |--------(n-1)------------|

which can be rewritten as aⁿ = a (a^n-1). This defines aⁿ in terms of itself, i.e., this is a recursive definition. The only thing we still need is a base condition, which is a⁰ = 1.

NOTE: Answers to the examples in this section of notes may be found in Notes 19 Answers.