Question

Design a recursive algorithm to compute a . We constructed an iterative algorithm to compute an in Example 8.5. aⁿ can be defined recursively as

Answer 1

The recursive definition can be expressed as a recursive solver for computing power(a, n).

The recursive process resulting from power(2, 5)

power (2, 5)

= 2 x power (2, 4)

= 2 x 2 x power (2, 3)

= 2 x 2 x 2 x power (2, 2)

= 2 x 2 x 2 x 2 x power (2, 1)

= 2 x 2 x 2 x 2 x 2 x power (2, 0)

= 2 x 2 x 2 x 2 x 2 x 1

= 2 x 2 x 2 x 2 x 2 = 2 x 2 x 2 x 4

= 2 x 2 x 8 = 2 x 16 = 32