Notes N19: Answers to Examples

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]

Contents

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., f0 = f1 = 1 [base case] and fn = fn-1+fn-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) =5___  fib(3) =3___ fib(2) =2___ fib(1) = 1 
{ELSE}	      {ELSE}       {ELSE}   \   {THEN}
     \  	    \		      \		
       \	      \___ fib(1)=1     fib(0) = 1
	 \		   {IF}		{IF}
	   \
              fib(2) =2___ fib(1) = 1
              {ELSE}       {IF}
		    \
		      \___ fib(0) = 1
			   {IF}
Thus f4 = 5.

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: 
      OLLEH

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);       |          1, -1
	   a = b;         |
	}                 |   p(1st call)
	int main()        |        a           b
	{                 |     1, 0, -1      0, -1
	   int x;         |
	   x = 1;         |   p(2nd call)
	   p(x);          |        a           b
	   cout << x << endl;     0, -1        -1
	}
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  prev, pprev, i, temp;
	   if ((n == 1) || (n == 0)) //base cases
		return 1;
	   else {

	       prev = 1;
	       pprev = 0;
	       for (i=1; i<=n; i++)
	          {
		     temp = prev + pprev;
		     pprev = prev;
		     prev = temp;
		   }
                return temp;
		
	   }
	}
	int main()
	{
	   int num,out;
	   cin >> num;
	   out = fib(num);
	   cout << "f sub " << num << " is " << out<< endl;
	   return 0;
	}

This page is maintained by Dennis C. Smolarski, S.J. dsmolarski@math.scu.edu
© Copyright 2002 Dennis C. Smolarski, SJ, All rights reserved. Last changed: 31 January 2002.