Recursion Studies

It is virtually impossible to provide practical programming solutions to a variety of complex problems without recursion. As such, it is an indispensable programming strategy.

The Key

Successful implementation of a recursive solution depends on your ability to define a recursive solution on paper. For example, the power function, xn can be defined non-recursively as,

xn= x×x×x×...×x (n times)

Defined recursively, we write,

(1)

From (1), the implementation is straightforward. Successful recursive solutions arise from the programmer being able to express a definition similar to (1) for each new problem, that includes both the general inductive substitution expression and a basis or stopping condition.

Examples

The table below suggests algorithms that lend themselves to recursive solutions. Develop methods to satisfy the stated purpose and a sample driver to test them.

Topic Purpose
Power Determines xn
Fibonacci Displays terms from a Fibonacci sequence
Sum of a Series Determines the sum of an arithmetic series using: Sn = tn+Sn-1
Palindrome Reverses the order of the characters in a String
Base Conversion Converts decimal numbers to any other base (<10)
Square Root: sqrt(x) Uses Newton's Method to approximate the square root
Pascal's Triangle Determines elements from Pascal's Triangle
Determinants Solves determinants recursively for use in Cramer's Rule
GCD Euclid's algorithm for determining the greatest common divisor
Matching Brackets Uses a stack to confirm matching brackets in an expression

Improved Power Method (Adapted from Data Structures and Algorithms, Goodrich and Tamassia)

The complexity of the power function function above is O(n). We can compute the power function much faster than this however, by using the following alternative recursive definition, which employs a squaring technique as illustrated by the following examples,

A close examination of the examples suggests that each recursive call to divides the exponent by two. Thus, there are O(log n) recursive calls, not O(n). That is, by combining recursion with the squaring technique, we reduce the running time for the computation of the power function from O(log n) to O(n) - a significant improvement.

Task.

  1. Look closely at the examples and compose a piecewise definition for xn similar to (1) above. (This is typically the key to a successful recursive implementation)
  2. Implement your definition above by completing the body of the power() method in this code.