Tutorial 3: Recursive Problem-Solving and Decomposition
Unit 1 ยท Section 3
Objectives
Break a problem into cohesive subproblems.
Identify base and recursive cases.
Trace recursion and compare alternatives.
Decomposition makes a problem manageable by assigning each part a clear responsibility. Recursion solves a smaller instance of the same problem and must progress toward a base case.
sum(n):
if n == 0 return 0
return n + sum(n - 1)
Exercises
Decompose a file-processing task.
Trace sum(4).
Rewrite a simple recursive sum iteratively and compare clarity.
Self-check
What is a base case?
Why must the input shrink?
What does decomposition improve?
Self-Check Quiz
1. What happens without a reachable base case?
AnswerRecursive calls continue until a stack overflow or another failure.
2. What is a subproblem?
AnswerA smaller, focused part of the original problem with a defined input and result.
Homework
Design recursive and iterative factorial algorithms.
Prove or explain termination.
Test zero, one, and invalid inputs.
Sample answerThe base case is factorial(0)=1; each call uses n-1, so non-negative input reaches zero. Negative input is rejected. The iterative version may use constant call-stack space while recursion mirrors the mathematical definition.