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,
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.
|
![]() |