# 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.
• 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.
• 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 recBint 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 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.

// 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);
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++)
} // method main

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)