I. In-Class Exercises

Programming Exercises

1. Decomposition of a Natural Number: L3091

II. Knowledge Summary

Core Idea

Recursive search solves problems by repeatedly splitting a large problem into smaller subproblems of the same kind. A recursive function calls itself until a base case is reached.

It is widely used in tree traversal, graph search, permutations, combinations, and similar problems with natural recursive structure.

Key Elements

Recursive search has two essential parts:

• Base case: the stopping condition
• Recursive step: how to reduce the problem size and move toward the base case

Important Notes

When writing recursive search:

• watch out for stack overflow
• avoid repeated computation
• convert to an iterative version when necessary

Memoization or dynamic programming can help when the same subproblem appears multiple times.

Common Types of Recursive Search

Depth-First Search

Used for traversing graphs and trees by going as deep as possible before backtracking.

Backtracking

Used for constraint satisfaction problems. If one choice fails, undo it and try another.

Binary Search

A recursive search technique on sorted arrays that reduces the search interval by half each time.

Execution Example

Decompose the natural number 4 into sums of positive integers in nondecreasing order:

4 = 1+1+1+1 = 1+1+2 = 1+3 = 2+2 = 4

Use the recursive function:

dfs(remaining, minimum_allowed)

1dfs(4, 1)
2|- choose 1 -> dfs(3, 1)
3|  |- choose 1 -> dfs(2, 1)
4|  |  |- choose 1 -> dfs(1, 1)
5|  |  |  `- choose 1 -> dfs(0, 1) -> output 1+1+1+1
6|  |  `- choose 2 -> dfs(0, 2) -> output 1+1+2
7|  |- choose 2 -> dfs(1, 2) -> no valid choice
8|  `- choose 3 -> dfs(0, 3) -> output 1+3
9|- choose 2 -> dfs(2, 2)
10|  `- choose 2 -> dfs(0, 2) -> output 2+2
11|- choose 3 -> dfs(1, 3) -> no valid choice
12`- choose 4 -> dfs(0, 4) -> output 4

The minimum_allowed restriction prevents duplicates such as both 1+3 and 3+1.

Problem-Solving Steps

When designing a recursive search:

1. Define the state: what do the function parameters mean?
2. Define the base case: when does recursion stop?
3. Enumerate choices: what options are available at each step?
4. Recurse with updated parameters
5. Prune branches that cannot lead to valid answers

Common Mistakes

• Missing or incorrect base cases
• Forgetting to undo a choice when using global state
• Enumerating duplicate states
• Passing parameters incorrectly
• Letting the search space explode without pruning

III. Homework

Programming Exercises

1. Splitting Natural Numbers: L3092