I. In-Class Exercises

Programming Exercises

1. Ackermann Function: L3081

II. Knowledge Summary

Iterative Recurrence

Recurrence here refers to solving a problem through repeated state updates in a loop. Each new state is derived directly from previous states through a recurrence formula.

Its core is to find the transition formula and compute forward step by step.

Recursion

Recursion means that a function calls itself to solve smaller subproblems of the same type, until reaching a base case.

It is especially natural for divide-and-conquer style problems.

Implementation Comparison

Recurrence / iteration:

• uses loops such as for or while
• updates states explicitly
• often matches the forward calculation process clearly

Recursion:

• the function calls itself
• requires a correct base case
• often expresses problem structure more elegantly

Performance and Resource Usage

Recurrence:

• better space efficiency
• usually faster because there is no function-call overhead

Recursion:

• consumes call stack space
• may cause stack overflow for deep recursion
• can be slower if there is heavy repeated computation

Typical Applications

Recurrence is suitable for:

• Fibonacci-style sequences
• simple summation problems
• many dynamic programming problems

Recursion is suitable for:

• quick sort
• merge sort
• search problems
• tree traversal

Comparison Table

Execution Example

Fibonacci with Recurrence

For F(6) with F(n)=F(n-1)+F(n-2), F(1)=1, F(2)=1:

Fibonacci with Recursion

1F(6)
2|- F(5)
3|  |- F(4)
4|  |  |- F(3)
5|  |  |  |- F(2)
6|  |  |  `- F(1)
7|  |  `- F(2)
8|  `- F(3)
9|     |- F(2)
10|     `- F(1)
11`- F(4)
12   |- F(3)
13   |  |- F(2)
14   |  `- F(1)
15   `- F(2)

Here F(4), F(3), and F(2) are recomputed many times.

Performance Comparison

Naive recursion is much slower, but memoization can optimize it to the same order as iteration.

Problem-Solving Steps

When solving a "derive the unknown from the known" problem:

1. Find the recurrence relation
2. Determine the initial values or base cases
3. Choose an implementation:
   • use iteration when the direction is clear and efficiency matters
   • use recursion when the problem naturally splits into subproblems
4. Add memoization if recursion repeats work

Common Mistakes

• Missing the recursion base case
• Setting wrong initial values
• Recursing too deeply and causing stack overflow
• Computing in the wrong direction
• Mixing 0-based and 1-based indices in recurrence arrays

III. Homework

Programming Exercises

1. Number of Moves in Tower of Hanoi: L3082