How does one develop a recursive algorithm? Here are some steps:
- Is recursion better than iteration? Recursion is appropriate if the problem being solved can be expressed as a series of smaller problems which are very similar. By using the solutions of each subproblem, the overall problem is solved. If an iterative solution can be created that uses less resources, then it should be strongly considered over the recursion algorithm.
- Define the base operations. How are the smaller, similar subproblems defined?
- Define the end condition. What stops the recursion? This condition should be tested before a recursive call is made.
- Does the recursion converge? Ensure that the algorithm moves closer to a terminal condition, and therefore a solution.
- Are there any special cases? handle special cases in addition to the terminal case.
Consider computation of a factorial:
- The overall problem n! can be represented in terms of subproblems (n-1)!
- The terminal condition is n=0 or 1
- The base operation is fact := n * fact(n-1)
- The special case of negative numbers is handled by passing positive value for n.
Here’s a Fortran program which reflects this:
recursive function fact(n) result(r) integer, intent(in) :: n integer r if (n < 0) then n = -n end if if (n == 0 .or. n == 1) then r = 1 else r = n * fact(n-1) end if end function fact