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

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;
}
}
```

Are fact(), fib() tail recursive?

What is it?

Write a recursive function which prints a reversed string

# 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?

Thomas P. Kelliher
Fri Feb 16 11:35:33 EST 1996
Tom Kelliher