By: Nicholas Duchon.

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.

- 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.

- 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.

- 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.

- "this" - in Java and other OO languages, an
instance-method call includes an instance of a class as part
of the context.
- 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,

- 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.

- 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 "
- 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 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.
- ED 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.

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.

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!

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)

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

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

- 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.

// SLOW

if (n == 0) return 0;

if (n == 1) return 1;

return addMe (n-1) + addMe (n-2);

// FAST using Pair class below

static Pair addMe2 (int n) {

if (n == 0) return new Pair (0, 0);

if (n == 1) return new Pair (1, 0);

Pair p = addMe2 (n-1);

return new Pair (p.a + p.b, p.a);

for (int i = 0; i < 200; i++)

System.out.printf ("%5d %,30d %,30d\n", i, addMe (i), addMe2 (i).a);

long a, b; // a = f(n-1), b = f(n-2)

a = x; b = y;

Part of the output if only addMe2 algorithm is printed:

87 679,891,637,638,612,258

88 1,100,087,778,366,101,931

89 1,779,979,416,004,714,189

90 2,880,067,194,370,816,120

91 4,660,046,610,375,530,309

92 7,540,113,804,746,346,429

93 -6,246,583,658,587,674,878

94 1,293,530,146,158,671,551

95 -4,953,053,512,429,003,327

96 -3,659,523,366,270,331,776

97 -8,612,576,878,699,335,103

(end)