1  Recursive Thinking and Recursive Functions

1.1  The idea

A recursive process is a process that calls itself.

To calculate 1·2 ·3 ºn, here is a process that works:

1. If n = 1 then the answer is 1.
2. If n > 1 then

   • Get the answer for 1·2 ·3 º(n-1)
   • Multiply this by n.

Step 2 is called the Recursive Step, the place where the process calls itself.

Here it is as a function in C++:

	int Multiply1ThruN (int N)
	   {
	   int answer = 0;
	   
	   if (N == 1)
	      answer = 1;                               //Exit step
	      
	   else if (N > 1)
	      answer = Multiply1ThruN (N - 1) * N;      //Recursive step
	      
	   return answer;
	   }

1.2  How it works in computer memory

If we call the above function with the statement:

	cout << Multiply1ThruN (3) << endl;

then what really happens?

The computer maintains in memory a sequential array called The Stack. Function calls and their arguments are placed on The Stack until they can be resolved into a return value.

cout << Multiply1ThruN (3) << endl; results in the following sequence of events:

1. Multiply1ThruN (3) is placed on The Stack. The Stack now looks like this:

   Multiply1ThruN (3)

2. In the Process of doing Multiply1ThruN (3) the computer must do Multiply1ThruN (2). This is placed on The Stack. The Stack now looks like this:

   Multiply1ThruN (3)

   Multiply1ThruN (2)

3. In the Process of doing Multiply1ThruN (2) the computer must do Multiply1ThruN (1). This is placed on The Stack. The Stack now looks like this:

   Multiply1ThruN (3)

   Multiply1ThruN (2)

   Multiply1ThruN (1)

4. In doing Multiply1ThruN (1), 1 is returned. The 1 replaces Multiply1ThruN (1). The Stack now looks like this:

   Multiply1ThruN (3)

   Multiply1ThruN (2)

   1

5. The computer takes the 1 and uses it to finish Multiply1ThruN (2). 2 is returned. The 2 replaces Multiply1ThruN (2) on TheStack. The Stack now looks like this:

   Multiply1ThruN (3)

   2

6. The computer takes the 2 and uses it to finish Multiply1ThruN (3). 6 is returned. The 6 replaces Multiply1ThruN (3) on TheStack. The Stack now looks like this:

   6

7. The computer grabs the 6 and puts it in place of Multiply1ThruN (3) in the statement cout << Multiply1ThruN (3) << endl;.

1.3  A Recursive Sort

Here is a recursive version of a simple sorting method, given a vector of positive ints in slots 0 through N and a place in the vector to start sorting:

The plan:

If there is just one number to sort

• Stop

else

• Find the smallest number after the starting position that is less than the number at the starting place.
• If you found such a number

  • Swap it with the number at the starting place.

• Sort the rest of the list.

The C++ code looks like:

	void RecursiveSort (vector <int>& numbers,    //List to sort
	                    int           startPlace) //Place to start sorting
	   {
	   //Purpose:  This function recursively sorts the list of numbers from
	   //            startPlace on down.
	   
	   if (startPlace < numbers.size ())
	   	  {
	   	  //Find the position of the smallest number AFTER the starting place.
	   	  
	   	  int posOfSmallest = FindPositionOfSmallest (numbers, startPlace + 1);
	   	
	      //If this number is smaller than the number at the starting place,
	      //  then swap it to the starting place.
	      
	   	  if (numbers [posOfSmallest] < numbers [startPlace])
	   	     SwapNumbers (numbers [startPlace], numbers [posOfSmallest]);
	   		
	   	  //Then sort the rest of the list.
	   	  
	   	  RecursiveSort (numbers, startPlace + 1);
	   	  }
	   }
	   
int FindPositionOfSmallest (vector<int>& numbers, int startPlace)
	   {
	   int smallest      = numbers [startPlace];
	   int smallPosition = startPlace;
	   
	   for (int n = startPlace; n < numbers.size (); n++)
	      {
	      if (smallest > numbers [n])
	         {
	         smallest      = numbers [n];
	         smallPosition = n;
	         }
	      }
	      
	   return smallPosition;
	   }
	   
	void SwapNumbers (int& one, int& two)
	   {
	   int temp = one;
	   
	   one = two;
	   two = temp;
	   }

1.4  More examples of Recursion

1. A function to compute xⁿ:

   int		PowerFn (int n, int exponent)
      {
      int returnVal;
      
      if (exponent == 0)
         returnVal = 1;                               //Exit step, n = 0
      else
         returnVal = n * PowerFn (n, exponent - 1);   //Recursive step
         
      return returnVal;
      }
   

2. A function to print out a triangle of *'s with n rows. (If n is 5 print

   *****
   ****
   ***
   **
   *

   																
   void   PrintTriangle (int n)
      {
      if (n == 1)
         {
         //Exit step
         
         cout << "*" << endl;         
         }
      else
         {
         //Now the recursive step:
         
         //Print the first row of n *'s
         //  Then print the remaining triangle with n - 1 rows 
         //  (same task one level down).
   
         for (int place = 1; place <= n; place++)
            cout << "*";
            
         cout << endl;
               
         PrintTriangle (n - 1);
         }
      }
   

3. A function to input and add up n numbers

   int      GetAndAddNumbers (int n)
      {
      int input, returnVal;
      
      if (n == 1)
         {
         //Exit step
         
         cout << "Enter a number";      
         cin  >> input;
         
         returnVal = input;
         }
      else
         {
         //Now the recursive step:
         
         //Get the first number, add it to the sum of the next n - 1 
         //   numbers (same task one level down).
         
         cout << "Enter a number";
         cin  >> input;
         
         returnVal = input + GetAndAddNumbers (n - 1);
         }
         
      return returnVal;
      }
   

4. A sequence of numbers is defined as a(n) = 3 a(n - 1) + 2 a(n - 2), with a(1) = 1 and a (2) = 2. (So the first 5 numbers would be: 1, 2, 8, 28, 100.) Compute the nth number in the sequence.

   int      Sequence (int n)
      {
      int returnVal;
      
      //There are two exit steps here, n = 1 and n = 2
      
      if (n == 1)
         returnVal = 1;      
         
      else if (n == 2)
         returnVal = 2;
         
      else
      
      //The Recursive Step requires the last two values:  
      //  the same task one level down, (n - 1), and also the same task
      //  two levels down, (n - 2).
      
         returnVal =  3 * Sequence (n - 1) + 2 * Sequence (n - 2);
         
      return returnVal;
      }
   

1.5  Problems:

1. Write a recursive function to sum up the cubes of all the numbers from 1 up through a given number.

2. The year: 1776.

   The place: the lines of the Continental Army under General Washington.

   The problem: You get up in the morning as usual, and to your great surprise, the year is 1776. CSM doesn't even exist and you haven't been born. (But I'll overlook this if you will.) Anyway, the Americans are in the middle of fighting a war to get independence from the bloody British.

   The bloody British are shelling the American position with a large cannon. As the General's chief of intelligence (quite an achievement for someone who hasn't been born!), you sneak into the bloody British camp to see how many cannon balls the bloody British have for that pesky cannon. You see that there is one stack of cannon balls arranged in layers. There is one ball at the top of the stack, 4 in the next layer, 9 in the next layer, then 16, and so on. The bloody British are getting suspicious, so you only have time to count the layers (there are 20) before you have to get out of there.

   When you get back to the American lines you want to impress General Washington, your boss. So you whip out your laptop computer, bring up your Poor Richard's C++ compiler, and write a recursive function to compute the solution. The General just won't be impressed with a for loop. (You are probably wondering where power for a computer could come from in 1776. The laptop is plugged into a lightning-attracting kite - learned that one from Ben Franklin.)

   What was the function?

3. Write a recursive function that will take a positive integer n and return the sum of its digits. (Remember: number % 10 is the first digit of a number, and number / 10 is the rest of the number.)

4. A number is entered into a program. The task: to convert it to its base 5 value. How to do this? Well, 1232 can be considered to be 2 + 3 * 5 + 2 * 5² + 1 * 5³. So the following algorithm works:
   1. If the number is less than 5, then this is the value.
   2. Else, the value is the first digit plus 5 * the base 5 value of the rest of the digits.

   Write a recursive function that returns the base 5 value of a given number. NOTE: In base 5 no digits can be more than 4. If the user enters such a thing, your program should catch it.

5. Euclid's algorithm for finding the largest positive integer that evenly divides two given positive integers (the Greatest Common Divisor, or GCD) is:
   1. Divide the larger by the smaller.
   2. If there is no remainder, the smaller is it.
   3. else, the smaller becomes the larger and the remainder becomes the smaller, and go back to a)

   Write a recursive function to find the GCD of any two given positive integers.

6. Write a recursive function to print out the prime factorization of a positive integer n. (So in case of n = 12, the output should be 2, 2, 3.)