There are lots of good examples of recursion and lots of resources on the web, so I want to give a very short introduction to some key aspects of recrusion that I hope will help make recursion a smaller issue and easier to comprehend.

What is recursion?

• It is a method being active more than once in a thread or process.
  
• Why is this an issue?
  
• In old languages, such as early common versions of Fortran, a function was only allowed to have one return address, which meant that recursion was impossible.
  
• Most modern languages, even newer versions of Fortran, use a calling stack with each call having its own return address, which makes recursion naturally available in the language.

What kinds of recursion are there?

• Direct - In direct recursion, a method explicitly calls itself.
  
• Indirect - In indirect recursion, a method calls another method, which will eventually call the first method again.
  
• Indirect recursion is common in large, complicated programs, particularly those with complicated GUI elements.
• Tail recursion
• the recursive call is the last statement in the method
• the recursive call only calls itself with different parameters
• defining a smaller problem
• the previous stack frame can be discarded
• because the local variables of the previous recursive step are no longer needed and can go out of scope
  

What are the key concepts in recursion?

• Parameters -
  
• a recursive algorithm almost always has at least one parameter which describes the problem, and
  
• is supposed to get smaller from one recursive call to the next.
• "this" - in Java and other OO languages,
  
• an instance-method call includes an instance of a class as part of the context.
  
• "this" instance can be considered part of the set of parameters used in the recursive call.
• Base case -
  
• When the parameter(s) reach a particular state,
  
•  the method should return some specific value,
  
• which should cause at least some (eventually all) of the recursive stack to unwind.
• Recursive or general case -
  
• This should "do some stuff" which involves a call to this method,
  
• or perhaps another method,
  
• with some "smaller" version of the problem,

What can go wrong?

• Infinite recursion -
  
• The recursive process does not stop.
  
• The points below are different reasons this might happen.
• Bad base case -
  • Maybe because all possible inputs were not considered and handled.
    
  • For example, if the inputs are supposed to be positive integers, the base case may only test for "==0" rather than "<=0".
  • Maybe because the stopping point test is not the desired one.
• Bad recursive case -
  • This case may not actually shrink the problem. It may in fact make the problem "bigger".
  • The algorithm could be just "wrong" - code compiles, runs and stops, but does not give the desired result.
• Zeno's paradox - The problem may get smaller each time, but may never actually reach the base case. For example:
  • Base case: x = 0
  • Recrusive sequence: 3/2 --> 5/4 --> 9/8 --> 17/16 --> ...
    
  • The values are 1+1/2^n of the previous case.
    
  • The values are getting smaller, but will never reach 0, since all the values are > 1.
    
• Near-infinite recursion -
  
• The algorithm with a particular set of parameters might be finite in a mathematical sense, but just too big for a real computer.
  
• In a real computer, this results in a Stack Overflow, or a segmentation fault (UNIX-type systems, meaning your process has used up its memory allocation),
  
• or just plain takes too long.
  

Debugging:

• Debugging recursive methods is notoriously difficult, but not impossible
• As with any debugging, one must be quite creative, and gather information either through the debugger or print statements. I generally find the latter easier to control.
• E5 example below shows a full class with a debugging flag and code embedded in the code. Of course, the problem might be with this code, but it can be used to limit the recursion level instead of letting a program run to stack overflow and a massive stack dump.

Examples:

These methods must be inside some class, of course, and they may be public or private, and they may be static or instance. I have left off all those modifiers in the early examples, since they are not relevant to the key issues we are considering in those examples.

E1: Simple recursion - one method calling itself once again:

int recA (int n) {
  if (n <= 0) return 1; // handles bad input and base case at once
  return n * recA (n-1); // the general case
} // end recA - computes n!

E2: GCD calculation

int gcd (int x, int y)
  if (y <= 0) return x
  return gcd (y, x%y)

Program:

public class GCD {
  public static void main (String [] args) {
    int a = 7503;
    int b = 9577;
    System.out.printf ("gcd(%d, %d) = %d\n",
        a, b, gcd(a,b));
  } // end main
 
  static int gcd (int x, int y) {
    if (y <= 0) return x;
    return gcd (y, x%y);
  } // end gcd
} // end class GCD

E3: Dual recursion - one method calls itself twice in the general case:

int comb (int n, int k) {
  if (k < 0) return 0; // the 3 BAD cases
  if (n < 0) return 0;
  if (n < k) return 0;

  if (k == n) return 1; // the two boundary = base cases
  if (k == 0) return 1;

  return comb(n-1, k-1) + comb(n-1, k); // the general case
} // end comb - computes combination of n things taken k at a time, C(n,k)

E4: Indirect recursion - the example makes little sense, but is easy to comprehend, at least

int recB (int n) {
  if (n <= 0) return 0;
  return n * recC (n-1);
} // end recB

int recC (int n) {
  if (n <= 0) return 1;
  return n + recB (n-1);
} // end recC

As an exercise, confirm that the following are correct:

• recB (5) = 65
• recC (5) = 25

E5: An example of bad recursion with some debugging code:

public class RecStop {
  static int count = 0;
  static boolean debugFlag = true;
  static int debugStop = 5;

  static int recD (int n) {
    if (debugFlag) {
      count ++;
      if (count >= debugStop) {
        System.out.println ("C: " + count);
        Thread.dumpStack ();
        System.exit(0); // get out of here!
      } // end if time to stop
    } // end if debug
    return recD (n+1);
  } // end recD

  public static void main (String args []) {
    recD (3);
  } // end main
} // end class RecStop

 E6: Adding: Fibonacci exponential and linear growth algorithms

• Note that addMe calls itself twice, so the total number of calls is one the order of 2^N, which gets huge quickly, and this code gets very slow somewhere around N=45.
• Also, the function overflows the long data type at N=93, reports negative numbers and then becomes just plain wrong after that point because of overflows.
• addMe2 uses the Pair class to return two numbers (f(n-1) and f(n-2)) at once, so the calls are linear, making only one recursive call, and the performance is much faster.
  
• Even at N=200 the program completes in almost the blink of an eye.
  
• But the overflow problem is the same as addMe, so none of the results after around the mid 40's are correct.