Recursion

Nicholas Duchon: Apr 17, 2018.

Examples

Applications

1. Walking a data structure
2. Linear - simple recursion will do
3. Tree - Tree Traversals
4. Binary trees - Prefix Example
5. Graphs
2. depth first
3. Graph traversal - Wikipedia
6. 2-D arrays
7. Permutations

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);
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 addMe1 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 90's are correct.
public class Adding {

// SLOW
static long addMe1 (int n) {
if (n == 0) return 0;
if (n == 1) return 1;
} // end method addMe1 - 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, addMe1 (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)