Recursion, Concepts and Examples

Tom Kelliher, CS23

Feb. 19, 1996

The Stack Model of Program Execution

How does a program use memory?

• Code --- code segment
• Static items --- data segment
• Local items --- stack (segment)
• Dynamic items --- heap

What's a stack?

Terminology:

• Push
• Pop
• Activation record

Contents of activation record:

1. Return address
2. Initialized actual arguments
3. Uninitialized locals
4. Return value
5. Stack bookkeeping info.

Created by calling function, used by called function

Idea:

1. Each time function called, activation pushed
2. Function executes (possibly causing further pushes)
3. Each time function returns, activation popped

Recursion

• What is it?
• Divide and conquer
• base case

What do I need?

1. Decomposition into smaller problems of same type
2. Recursive calls must diminish problem size
3. Necessity of base case
4. Base case must be reached

Box Trace Example

Consider the code fragment:

main()
{
   int i = 4;                 // 1
   cout << f(i) << endl;      // 2
   i++;                       // 3
   cout << f(i) << endl;      // 4
}

int f(int a1)
{
   if (a1 <= 1)               // 5
      return 1;               // 6
   else                       // 7
      return a1 * f(a1 - 1);  // 8
}

Box trace yourselves:

#include <iostream.h>

int BinSearch(const int A[], int First, int Last,
              int Value)
// ---------------------------------------------------------
// Searches the array elements A[First] through A[Last] 
// for Value by using a binary search.
// Precondition: 0 <= First, Last <= SIZE - 1, where
// SIZE is the maximum size of the array, and
// A[First] <= A[First+1] <= ... <= A[Last].
// Postcondition: If Value is in the array, returns
// the index of the array element that equals Value;
// otherwise returns -1.
// ---------------------------------------------------------
{
   if (First > Last)
      return -1;      // Value not in original array

   else
   {  // Invariant: If Value is in A, 
      //            A[First] <= Value <= A[Last]
      int Mid = (First + Last)/2;
      if (Value == A[Mid])
         return Mid;  // Value found at A[Mid]

      else if (Value < A[Mid])
         return BinSearch(A, First, Mid-1, Value);  // X

      else
         return BinSearch(A, Mid+1, Last, Value);   // Y
   }  // end else
}  // end BinSearch

Assume the array holds: 1, 5, 9, 12, 15, 21, 29, 31

Search for: 5, 13

Efficiency of Recursion

Costs:

• Function call, return
• Repeated solution of same sub-problems

Consider:

int fib(int val)
{
   if (val <= 2)
      return 1;
   else
      return fib(val - 1) + fib(val - 2);
}

Call graph for fib(6):

Tail Recursion

A function is tail recursive if the very last thing it does is make its recursive call.

Example:

void printLinkedList(list* l)
{
   if (l != NULL)
   {
      cout << l->fname << " " << l->lname << endl;
      printLinkedList(l->next);
   }
}

Are fact(), fib() tail recursive?

Head Recursion

What is it?

Write a recursive function which prints a reversed string

Is it head recursive?

Utility of head recursion

Example

Write a recursive function which computes pow(n, i).

int pow(int n, int i)
{
   if (i == 0)
      return 1;
   else if (i == 1)
      return n;
   else
   {
      int partial = pow(n, i / 2);

      if (i % 2 == 0)
         return partial * partial;
      else
         return partial * partial * n;
   }
}

More efficient than iterative solution?