length of sequence = { sizes, eventually the sub-problem becomes small enough to be solved directly, without recursion. Therefore, a recursive solver has two cases: . Base case: The problem size is small enough to be solved directly. Output the solution.
There must be at least one base case. . Recursion step: The problem size is not small enough. Deconstruct the problem into a sub-problem, strictly smaller in size than the given problem.
Call a sub-solver to solve the sub- problem. Assume that the sub-solver outputs the solution to the sub- Chapter Page - - problem. Construct the solution to the given problem. This outline of recursive problem solving technique is shown below.
solver (input) if input is small enough construct solution else find of reduced input solutions to = solver for each construct solution to the problem from solutions to the Whenever we solve a problem using recursion, we have to ensure these two cases: In the recursion step, the size of the input to the recursive call is strictly smaller than the size of the given input, and there is at least one base case. . . Recursion — Examples Example .
. The recursive algorithm for length of a sequence can be written as length (s) -- inputs : s -- outputs : length of s if s has one customer -- base case else + length(tail(s)) -- recursion step Example . . Design a recursive algorithm to compute a n .
We constructed an iterative algorithm to compute a n in Example . . a n can be defined recursively as a n = if n = a × a n - otherwise The recursive definition can be expressed as a recursive solver for computing power(a, n). power (a, n) -- inputs: n is an integer , n ≥ -- outputs : a n if n = -- base case else --recursion step a × power (a, n- ) The recursive process with solvers for calculating power( , ) is shown in Figure .