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.
public class Adding {
// SLOW
static long addMe (int n) {
if (n == 0) return 0;
if (n == 1) return 1;
return addMe (n-1) + addMe (n-2);
} // end method addMe -recursion returning one number
// 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);
} // end method addMe2 - recursion returning 2 numbers
public static void main(String[] args) {
for (int i = 0; i < 200; i++)
System.out.printf ("%5d %,30d %,30d\n", i, addMe (i), addMe2 (i).a);
} // method main
} // end class Adding
class Pair {
long a, b; // a = f(n-1), b = f(n-2)
public Pair (long x, long y) {
a = x; b = y;
} // end 2 long constructor
} // end class Pair
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)