Recursion

Nicholas Duchon: Apr 17, 2018.

Outline

Examples

  1. n!
  2. GCD (a, b)
  3. C(n, k)
  4. Indirect
  5. Bad
  6. Fibonacci

Applications

  1. Walking a data structure
  2. Linear - simple recursion will do
    1. Tower of Hanoi - Wikipedia
  3. Tree - Tree Traversals
  4. Binary trees - Prefix Example
  5. Graphs
    1. breadth first
    2. depth first
    3. Graph traversal - Wikipedia
  6. 2-D arrays
    1. mazes
      1. Maze generation algorithm - Wikipedia
      2. Maze solving algorithm - Wikipedia
    2. Recursion Blobs
  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?

What kinds of recursion are there?

What are the key concepts in recursion?

What can go wrong?

Debugging:


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:

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

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)