Recursion

• A recursive function is a function that calls itself.
• Many tasks can be done with either recursion or with iteration
  • iteration involves a loop, but not recursive calls
• When using a loop, one should always allow a "way out" (avoid infinite looping
• Similarly, when using recursion, make sure there's a way out
  • "Infinite" recursion will actually result in a crash, when the activation records (from function calls) overrun the stack
  • At some point, the function has to stop calling itself and be allowed to exit (each instance of the function returns to the previous instance -- unwinding the stack)

A typical example: Factorials

• n! is defined as n * (n-1) * (n-2) * ... * 1.
• We can define a factorial function (iteratively) as follows:

     unsigned long Factorial(int n)
     {
        unsigned long f = 1;
        for (int i = n; i >= 1; i--)
           f *= i;
  
        return f;		// this is the answer
     }
  

• But notice also that:

    n! = n * (n-1)!
  

• By using this formula, we can define a factorial function recursively:

     unsigned long Factorial(int n)
     {
  	if (n <= 1)	// base case
  	   return 1;
  	else
  	   return (n * Factorial(n-1));
     }
  

• The recursive version of the function calls itself, but it will eventually stop calling itself once we get down to n = 1.
• Notice that each recursive call will invoke the function for a smaller value of n. Namely, n-1 ).
• So, which is better?
  • In this case, they are close to the same in performance
  • Same number of "recursive" function calls as loop iterations, typically
  • Recursive version incurs a little extra overhead (activation records on the function call stack)

Is Recursion Better?

• Which is better? Recursion or iteration? Depends on the situation!
• Look at this example -- the Fibonnaci sequence
• The Fibonnaci sequence itself is defined recursively:
  • First and second sequence elements are both 1.
  • In general, the Nth sequence element is defined to be the sum of elements N-1 and N-2
  • More formally: Fib(n) = Fib(n-1) + Fib(n-2), where the argument is the element number of the sequence (1st, 2nd, 3rd, etc)
• So does this mean the recursive solution is the best? Compare the iterative solution with the recursive solution
• Iterative Fibonnaci function:

    int Fib(int n)
    {
       int n1 = 1, n2 = 1, n3;
       int i = 2;
       while (i < n)
       {
          n3 = n1 + n2;
          n1 = n2;
          n2 = n3;
          i++;
       }
       return n2;
    }
  

• Recursive Fibonnaci function:

    int Fib(int n)
    {
      if (n <= 0)		return 0;	// base case	
      else if (n == 1)    return 1;	// base case
      else
  	return Fib(n-1) + Fib(n-2);	// recursive computation
    }
  

• Which one is more efficient?
  • One of these is DEFINITELY more efficient than the other
  • Why?
  • Try them out
  • Looks like the iterative version wins this race!
• Comparing recursion and iteration
  • Any problem that can be coded with a recursive solution can also be done iteratively with a loop
  • Often, a recursive function is easier to WRITE!
  • Recursion does involve extra overhead (function calls, activation records on the program call stack)
  • So, with equivalent recursive and iterative solutions, the iterative one usually is slightly more efficient
  • In some case, the RUN time of one is more efficient than the other, giving us a clearer choice

Sorting algorithms

• There are many solutions to sorting a list, like an array
• You've probably seen:
  • Bubble sort
  • Selection sort
• Two sort algorithms (usually written with recursion) that have much better performance time:
  • Quicksort
  • Merge sort
• These two are generally considered to be the fastest sort algorithms to choose from -- and the recursive versions are easier to write

Examples from textbook (Savitch)

Examples from a former textbook (Gaddis)

• Simple example illustrating syntax
• Factorial
• Recursive function that counts appearances of a letter in a string
• One of the common GCD algorithms
• Recursive Fibonnaci -- YUCK!
• Recursive version of binary search (on an array)
• Towers of Hanoi
• Quicksort
• Making change (coins) -- search through all combinations