Recursion in Data Structures

Introduction to Recursion

Definition of Recursion: Recursion is a technique sometimes used to solve a problem by first solving a smaller version of the exact same problem. It involves solving a problem by solving a smaller problem of the same type.
Recursive Functions: When this technique is implemented in software, it results in functions that call themselves.
Example Recursive Function Structure:

$int\,f(int\,x) \{$ $int\,y;$ $if(x==0)$ $return\,1;$ $else\, \{$ $y = 2 \times f(x-1);$ $return\,y+1;$ $\}$ $\}$

Recursively Defined Problems: Factorials

Recursive Solution for $n!$ (n factorial):
- $1 \text{ if } n = 0$
- (n-1)! \times n \text{ if } n > 0
Closed-Form Solution for $n!$ :
- $1 \text{ if } n = 0$
- 1 \times 2 \times 3 \times \dots \times (n-1) \times n \text{ if } n > 0

Coding and Tracing the Factorial Function

Recursive Implementation in C++:

$int\,Factorial(int\,n) \{$ $if (n==0) \, \text{// base case}$ $return\,1;$ $else$ $return\,n \times Factorial(n-1);$ $\}$

Tracing $5!$ :
- $5 \times 4!$
- $4! = 4 \times 3!$
- $3! = 3 \times 2!$
- $2! = 2 \times 1!$
- $1! = 1 \times 0!$
- $0! = 1 \, \text{(base case reported)}$
- Values are returned up the chain:
  - $1! = 1 \times 1 = 1$ is returned.
  - $2! = 2 \times 1 = 2$ is returned.
  - $3! = 3 \times 2 = 6$ is returned.
  - $4! = 4 \times 6 = 24$ is returned.
  - $5! = 5 \times 24 = 120$ is returned.
- Final Value: $120$
Iterative Implementation in C++:

$int\,Factorial(int\,n) \{$ $int\,fact = 1;$ $for(int\,count = 2; count \le n; count++)$ $fact = fact \times count;$ $return\,fact;$ $\}$

Combinations (n choose k)

Problem Definition: Given $n$ things, how many different sets of size $k$ can be chosen?
Recursive Solution:
- $\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}$ for 1 < k < n
Base Cases:
- $\binom{n}{1} = n$
- $\binom{n}{n} = 1$
Closed-Form Solution:
- $\binom{n}{k} = \frac{n!}{k!(n-k)!}$ for 1 < k < n

Recursive Implementation of Combinations

C++ Code:

$int\,Combinations(int\,n, int\,k) \{$ $if(k == 1) \, \text{// base case 1}$ $return\,n;$ $else\,if\,(n == k) \, \text{// base case 2}$ $return\,1;$ $else$ $return(Combinations(n-1, k) + Combinations(n-1, k-1));$ $\}$

Example Trace: Combinations(4, 3):
- $= Combinations(3, 3) + Combinations(3, 2)$
- $= 1 + (Combinations(2, 2) + Combinations(2, 1))$
- $= 1 + (1 + 2)$
- Final Result: $4$

Recursion vs. Iteration

Conceptual Differences:
- Iteration uses a looping construct.
- Recursion uses a branching structure.
Efficiency Concerns:
- Recursive solutions are often less efficient than iterative solutions in terms of both time and space.
- Recursion involves overhead from multiple function calls.
Simplification: Recursion can simplify the solution of a problem, frequently resulting in shorter and more easily understood source code.

How to Write a Recursive Function

Essential Steps:
1. Determine the size factor: Identify what makes the problem smaller.
2. Determine the base case(s): Identify the version for which you already know the answer.
3. Determine the general case(s): Identify where the problem is expressed as a smaller version of itself.
4. Verify the algorithm: Use the "Three-Question-Method."

The Three-Question Verification Method

The Base-Case Question: Is there a non-recursive way out of the function, and does the routine work correctly for this base case?
The Smaller-Caller Question: Does each recursive call to the function involve a smaller case of the original problem, leading inescapably to the base case?
The General-Case Question: Assuming that the recursive call(s) work correctly, does the whole function work correctly as a whole?

Recursive Binary Search

Iteration vs. Recursion:
- The non-recursive implementation uses a while loop: while((first <= last) && !found).
Recursive Attributes:
- Size Factor: The number of elements in the range (info[first] ... info[last]).
- Base Case 1: If first > last, return false (item not found).
- Base Case 2: If item == info[midPoint], return true (item found).
- General Case:
  - If item < info[midPoint], search the first half.
  - If item > info[midPoint], search the second half.
Recursive Implementation in C++:

$template$ $bool\,BinarySearch(ItemType\,info[], ItemType\&\,item, int\,first, int\,last) \{$ $int\,midPoint;$ if(first > last) \, \text{// base case 1} $return\,false;$ $else \{$ $midPoint = (first + last)/2;$ if(item < info[midPoint]) $return\,BinarySearch(info, item, first, midPoint-1);$ $else\,if (item == info[midPoint]) \{ \, \text{// base case 2}$ $item = info[midPoint];$ $return\,true;$ $\}$ $else$ $return\,BinarySearch(info, item, midPoint+1, last);$ $\}$ $\}$

Wrapper Function:

$template$ $void\,SortedType::RetrieveItem (ItemType\&\,item, bool\&\,found) \{$ $found = BinarySearch(info, item, 0, length-1);$ $\}$

Implementation of Recursion Mechanics

Function Call Process:
1. Executing the current function is paused.
2. An activation record is stored on the run-time stack. This record contains variables, parameters, and the return address (the place to start executing upon return).
3. Actual parameters are bound to formal parameters.
4. Control is transferred to the called function.
Function Return Process:
1. After execution, the activation record is popped off the run-time stack.
2. Old values of parameters and variables are restored.
3. The return value replaces the function call in the assignment statement/expression.
Recursive Call Mechanics: There is no fundamental difference between recursive and non-recursive calls, except the calling and called functions share the same name.
Trace Example for $f(3)$ :
- f(3) calls f(2). Stack pushes f(3) details.
- f(2) calls f(1). Stack pushes f(2) details.
- f(1) calls f(0). Stack pushes f(1) details.
- f(0) returns $1$ .
- f(1) pops, y = 2 * 1 = 2, returns y + 1 = 3.
- f(2) pops, y = 2 * 3 = 6, returns y + 1 = 7.
- f(3) pops, y = 2 * 7 = 14, returns y + 1 = 15.
- Value Returned: $15$ .

Recursive Item Insertion in a Sorted List

Comparison to Iterative Implementation: Previous iterative implementations required a predLoc (predecessor location) pointer to insert a new node. Recursive implementation simplifies this.
Recursive Attributes:
- Size Factor: Number of elements in the current sub-list.
- Base Case 1: List is empty.
- Base Case 2: item < location->info. The item should be inserted at the beginning of the current sub-list.
- General Case: Insert(location->next, item).
Recursive Implementation in C++:

$template$ $void\,Insert(NodeType*\,\&location, ItemType\,item) \{$ if((location == NULL) || (item < location->info)) \{ \, \text{// base cases} $NodeType*\,tempPtr = location;$ $location = new\,NodeType;$ location->info = item; location->next = tempPtr; $\}$ $else$ Insert(location->next, item); \, \text{// general case} $\}$

Note on Pointers: By using a reference to a pointer (NodeType<ItemType>* &location), the function can modify the next member of the previous node directly, eliminating the need for predLoc trackers.

Recursive Item Deletion in a Sorted List

Recursive Attributes:
- Size Factor: Number of elements in the list.
- Base Case: item == location->info. Delete the node pointed to by location.
- General Case: Delete(location->next, item).
Recursive Implementation in C++:

$template$ $void\,Delete(NodeType*\,\&location, ItemType\,item) \{$ if(item == location->info) \{ $NodeType*\,tempPtr = location;$ location = location->next; $delete\,tempPtr;$ $\}$ $else$ Delete(location->next, item); $\}$

Efficiency and Decision Criteria

The Problem of Redundancy: Recursion can be very inefficient in some cases. For instance, in Comb(6, 4), many identical sub-calls like Comb(3, 2) and Comb(2, 1) are re-calculated multiple times across the recursion tree.
When to Use Recursion:
1. The depth of recursive calls is relatively shallow.
2. The recursive version performs approximately the same amount of work as the non-recursive version.
3. The recursive version is significantly shorter and simpler than the non-recursive solution.