LAB 10
Recursion

A.  What is Recursion?
B.  Recursion Guidelines
C.  How Recursion is Implemented
D.  Recursion and Iteration
E.  Recursion and Efficiency

Functions that call themselves are said to be recursive functions.  Therefore, recursion is a problem solving technique that allows a function to call itself and this technique can be applied when the solution to a problem can be stated in terms of itself.  In this lab we will examine some problems that can be stated in terms of themselves and show how these functions can be written recursively.

Example: Computing n! (n factorial)

The classic example of a problem where the solution to the problem can be stated in terms of itself is the calculation of n factorial for n >= 1.  By definition:

n! = 1 * 2 * 3 * .. * n-1 * n 

or alternatively, by reversing the order of multiplications:

n! = n * n-1 * .. * 3 * 2 * 1 

Notice that to calculate n factorial recursively, we calculate n - 1 factorial and multiply by n.  To calculate n-1 factorial we calculate n - 2 factorial and multiply by n - 1, etc.  For example,

         4! = 4 * 3!
            = 4 * 3 * 2!
            = 4 * 3 * 2 * 1!
            = 4 * 3 * 2 * 1

To calculate factorial we need a definition.  The following is a recursive definition of factorial:

        n! = 1,             if n = 0
        n! = n * (n - 1)!,  if n > 0

A recursive definition consists of a base case step that defines the beginning elements in the set and a recursive step that expresses the relationship between elements in the set.

Here is a recursive C++ function to calculate n!  Notice how closely it follows the recursive definitions of factorial as shown above.

       // Recursive factorial function.  Assume n >= 0.
       int fact(int n)
       {
           if (n == 0)
               return (1);
           else
               return (n * fact(n - 1));
       }

The value of fact(4) is calculated as follows:

fact(4) = 4 * fact(3)
    fact(3) = 3 * fact(2)
        fact(2) = 2 * fact(1)
            fact(1) = 1 * fact(0)
                fact(0)  is 1 (base case)

When the computer reaches the base case fact(0), there are three suspended computations. After calculating the value returned for the stopping case, it resumes the most recently suspended computations to determine the value of fact(1). After that, the computer completes each of the suspended computations, using each value computed as a value to plug into another suspended computation, until it reaches and completes the computation for the original call fact(4). The details of the final computation are illustrated below:

Since fact(0) = 1, then fact(1) = 1 * 1 = 1
Since fact(1) = 1, then fact(2) = 2 * 1 = 2
Since fact(2) = 2, then fact(3) = 3 * 2 = 6
Since fact(3) = 6, then fact(4) = 4 * 6 = 24

A.	Functions that call themselves are said to be
		__________ functions.

B.	What would be the output that would result from
			cout << f(2);
		given the function 
			int f(int n)
			{
				if (n == 1)
					return 2;
				else if (n == 2)
					return 3;
				else
					return (f(n-1)*f(n-2));
			}

C.	What does the following calculate?
		int f(int n)
		{
			if (n==1)
				return 4;
			else
				return (4*f(n-1));
		}

	a.	4n
	b.	4n
	c.	n4
	d.	4 + n

D.	A recursive definition has a __________ step that defines
 the beginning elements in the set.

E. 	How many times would f be called recursively if initially
		main called f(4)?
		int f(int n)
		{
			if (n==1)
				return 4;
			else
				return (4*f(n-1));
		}

Writing recursive functions is sometimes not an easy accomplishment for the beginning programmer.  The most common mistake that beginning programmers make is writing recursive functions that continue to make recursive calls --- meaning the program will never terminate.  Therefore, caution needs to be taken to assure that the function will eventually stop calling itself.  Let's observe some simple guidelines to aid in writing recursive functions.

1. A recursive function must call itself; i.e. the function fact calls the function fact.
2. At each successive call to the recursive function, the "size" of the problem is diminished. The next call to fact solves a problem that is identical in nature to the original problem but smaller in size.
3. There is one instance of the problem that is treated differently from all of the others. This special case is called the base case or the stopping condition and the solution to the problem is known in that particular case. The base case allows recursion to stop.
4. The manner in which the size of the problem is reduced must cause the base case to be reached.

Example:   Fibonacci Sequence

There is a pattern here. The number of rabbits at the beginning of month m is the sum of two previous months (since we have all those grown the last month plus babies from all those from the previous month).  These numbers

1, 1, 2, 3, 5, 8,...

A.	What is the next number in the Fibonacci sequence that begins 
		1,1,2,3,5,8

B.	Complete the recursive definition of the Fibonacci sequence.
		f(n) = 1		for n = 1
		f(n) = 1		for n = 2
		f(n) = f(n-1) + ______	for n > 2


C.	What does the following calculate?
		int f(int n)
		{
			if (n==1)
				return 1;
			else
				return (n + f(n-1));
		}
	a.	n!
	b.	n2
	c.	nn
	d.	the sum of the numbers from 1 to n inclusive

       $ script lab10ex3.log
       $ pr -n -t -e4 lab10a.cpp
       $ c++ lab10a.cpp -o lab10a
       $ lab10a < $CLA/lab10a0.dat
       $ lab10a < $CLA/lab10a1.dat
       $ lab10a < $CLA/lab10a2.dat
       $ exit

A. 	What is the base case in the following definition?
		f(n) = 2		for n = 1
		f(n) = 2*f(n-1)		for n > 1

	a.	f(1) = 2*f(n-1)
	b.	f(n) = 2*f(n-1)
	c.	f(n) = 2
	d.	f(1) = 2

B. 	How many times would the function f be called recursively
		if initially main called f(5)?
		int f(int n)
		{
			if (n == 1)
				return 2;
			else if (n == 2)
				return 3;
			else
				return f(n-1) * f(n-2);
		}

A recursive function call, like any function call, causes certain data to be placed on the system stack.  A stack is a data structure such that the first item referenced or removed is always the last item entered into the stack. It is like a stack of plates in a cafeteria. When a plate is added to the stack, it is added to the top. When a plate is removed from the stack, it is removed from the top of the stack and is the plate that was added most recently.

A recursive call causes the return address to be added to the system stack as well as the current value of all local variables because when the return occurs these variables must be set back to their value before the call.  For example, given the following recursive function

     // An example of recursion.
     void procA(int n)
     {
        int x;
        x = 5 + n;
        if (n == 1)
            return x;
        else
            return (n*procA(n - 1));
     }

A.	(T/F) A stack is a data structure in which the first item 
		entered is always the first item removed.



B.	Given the following recursive function, what output would
		result from the execution of
			cout << procA(3);
		int procA(int n)
		{
			int x;
			x = 5 + n;
			if (n==1)
				return x;
			else
				return(n*procA(n-1));
		}

C.	Given the following recursive function, what is output by the execution of
			cout << procA(3);

		void procA(int n)
		{
			int x;
			x = 20;
			if (n==2)
			{
				x = x%2;
				procA(n-1);
				cout <<”x= “ << x << “\tn = “ << n << endl;
			}
			else if (n==1)
				cout << “n = “ << n << endl;
			else
				procA(n-1);
			cout << “End of procA, n = “ << n << endl;
		}

	a.	n = 1
		End of procA n = 1
		x = 0	n = 2
		End of procA n = 2
		End of procA n = 3

	b.	End of procA n = 3
		x = 0	n = 2
		End of procA n = 2
		n = 1
		End of procA n = 1

	c.	n = 1
		x = 0	n = 2
		End of procA n = 3

	d.	none of the above



D. 	(T/F) A recursive call must place all global variables on
		the stack so they can be reset upon return.


E. 	Given a recursive call to the function procB, name 
	everything that would have to be put on the stack?
		void procB(int n)
		{
			int m;
			float p;
			m = 2n;
			p = n-4;
			if ((n==1)||(n++2))
				return (n+1);
			else
				return(m+p*procB(n-1));
		}
	a.	m and p
	b.	m, p, and the instruction pointer
	c.	m, n, p, and the instruction pointer
	d.	the instruction pointer

Many older programming languages (like BASIC, COBOL, and FORTRAN) do not support recursion.  One can implement recursion by stacking variable values on a stack and restoring them upon return.  It is a somewhat complicated process and used only when necessary.

Some languages like LISP (also quite old) use recursion almost exclusively. The only way to loop in some older versions of LISP was by using recursion. You should understand that recursion often replaces a loop. It is rare to find a recursive call inside a loop (in simple programs). Such a design is a common error of those who are not adept at using recursion.   Be careful!  Here, for instance, is an iterative procedure that might be contained in a ListClass implementation file to print a linked list.

     // Print list using a loop
     void ListClass::printIter(Node * p)
     {
          p = head;
          while (p != NULL)
          {
              cout << p->data;
              p = p->next;
          }
     }

Notice there is no loop here other than the recursion.   Also, note that, usually, recursive functions are called by non-recursive functions since they must receive a private data member of the class (the head of the list) to start executing. For example, the printRecursive() function above should be called by a "helper" function, say print() as shown below:

    void ListClass::print()
    {
         printRecursive(head);
    }

A.	Which of the following DO NOT support recursion?
	a.	C++
	b.	FORTRAN
	c.	LISP
	d.	All of the above support recursion


B.	(T/F)  The following would correctly print the nodes
		in a linked list.
	void ListClass::printNodes(Node* p)
	{
		p = head;
		while (p != NULL)
		{
			cout << p->data;
			printNodes(p->next);
		}
	}	


C.	Which of the following would be the correct recursive 
	function for counting the nodes in a linked list?

	a.	int f(node* p)
		{
			if (p != NULL)
				return (1+f(p->next));
			else
				return 0;
		}

	b.	int f(node* p)
		{
			return (1+f(p->next));
		}

	c.	int f(node* p)
		{
			if (p->next == NULL)
				return 0;
			else
				return (1+f(p->next));
		}

	d.	  None of the above

E. Recursion and Efficiency

  Each of the examples above have been very simple to provide a solid understanding of recursion. Unfortunately, each of the examples presented so far are inefficient. In most implementations of C++, a function call causes a certain amount of record keeping overhead to place items on the system stack before the call and to remove the items upon return to the calling function. Since recursion causes many function calls, this increases record keeping overhead even more. Secondly, some recursive algorithms are very inefficient. This has nothing to do with the overhead of the function calls but has to do with the method of solution the function uses. For example in the recursive solution for the multiplying rabbits problem, a portion of the diagram for computing fib(6) might look like that below:

As you can see from this diagram, the problem with  fib is that it computes the same values over and over again. If the diagram were completed, you would be able to see that fib(6) causes fib(2) to be computed 5 times. When n is fairly large, many of the values are recomputed millions of times! This huge number of computations makes the computation very inefficient.

As can be seen in the previous discussion, recursion can be very inefficient. However, recursion is truly valuable when a problem has no simple iterative solution. In the following section, we will discuss the use of recursion on a problem for which it is very difficult to determine a non-recursive solution.

Section omitted (uses linked lists in example).

Exercise 7: Load the files lab10b.cpp, main10b.cpp, and lab10b.h to your account. Modify lab10b.cpp by writing a recursive function countAll(node* ptr) that will count the nodes within the data structure. CountAll should count the node pointed by ptr. Then count all the nodes in the left data set, then count all the nodes in the right data set. Turn in a script log with a cat of lab10b.cpp, a compile, and three runs with the data files $CLA/lab10b0.dat, $CLA/lab10b1.dat, and $CLA/lab10b2.dat. When you run your program use redirection to read from the various files.

A. 	(T/F) It is common practice to place a recursive call inside a loop.


B. 	(T/F)  The following recursive function calculates the same
		   thing as the iterative function below it.
		int recurse(int n)
		{
			if (n==1)
				return 2;
			else
				return (2*recurse(n-1));
		}

		int iterate(int n)
		{
			int s = 2;
			for(int i=2;i<=n;i++)
				s = 2*s;
			return s;
		}