How to develop a recursive algorithm

How does one develop a recursive algorithm? Here are some steps:

  1. 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.
  2. Define the base operations. How are the smaller, similar subproblems defined?
  3. Define the end condition. What stops the recursion? This condition should be tested before a recursive call is made.
  4. Does the recursion converge? Ensure that the algorithm moves closer to a terminal condition, and therefore a solution.
  5. 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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.