Intro to Recursion

"In order to understand recursion, one must first understand recursion."

Concept

• Conceptually: Compute a solution to a problem by first computing solutions to smaller instances of the same problem (using the same technique)
• Practically: A method that calls itself (usually directly)
• Divide and Conquer
• Recursion works by modifying a set of data until a certain base condition(s) is met
• Recursive calls are placed on the runtime stack so that the results of each call are stored in the order they're called
• Use base cases to avoid infinite recursion
• The recursive step in general moves towards the base case

In Math: Recurrence Relations

Fibonacci numbers

F_n = F_{n - 1} + F_{n - 2}
which leads us to
F₂ = F₁ + F₀
F₃ = F₂ + F₁
F₄ = F₃ + F₂
... etc

Examples in Computer Science

Handing Out Papers - Iterative

handOutPapers(pile):
  student = first student in line
  while pile is not empty:
    paper = pile.pop() 
    give paper to student
    student = next student in line

Handing Out Papers - Recursive-A

handOutPapers(pile):
  if pile is not empty:
    paper = pile.pop()
    keep paper
    next = next student in line
    next.handOutPapers(pile)

• Pile gets smaller each time (due to pop())
• Each student follows the same algorithm
• Algorithm stops when pile is empty?

Handing Out Papers - Recursive-B

handOutPapers(pile):
  paper = pile.removeTop()
  keep paper
  if pile is not empty:
    next = next student in line
    next.handOutPapers(pile)

• More descriptive of real life
• But what happens when a student is handed an empty pile?

Handing Out Papers - Recursive-C

handOutPapers(pile): if pile is not empty: paper = pile.removeTop() keep paper if pile is still not empty: next = next student in line next.handOutPapers(pile)

• Original was simpler
• Often simpler to code if stop on empty or 0

Lots and Lots

public class CodeD {
  public static void main(String[] args) {
    lotsAndLots(0);
  }

  public static void lotsAndLots(int num) {
    System.out.println(num);
    lotsAndLots(num + 1);
  }
}

• What happens in the above code?
• Is it correct?

Printing Digits N - 1 (A)

public static void printDigits(int n) {
  if (n == 0) {
    return;  //base case: do nothing
  }else {
    System.out.println(n);
    printDigits(n - 1);  //recursive call on smaller problem
  }
}

• What would printDigits(3) do?
• What would printDigits(-1) do?
• What if we swap the order of the two lines in the else...?
• Visualization in Python

Printing Digits 1 - N (B)

public static void printDigits(int n) {
  if (n <= 0) {
    return;  //base case: do nothing
  }else {
    printDigits(n - 1);    //recursive call on smaller problem
    System.out.println(n); //print after returning from recursion
  }
}

• Updated test in if
• Swapped two lines

Printing Digits 1 - N (C)

public static void printDigits(int n) {
  if (n <= 0) {
    return;  //base case: do nothing
  }
  printDigits(n - 1);    //recursive call on smaller problem
  System.out.println(n); //print after returning from recursion
}

* Note that the else is missing

Printing Digits 1 - N (D)

public static void printDigits(int n) {
  if (n > 0) {
    printDigits(n - 1);    //recursive call on smaller problem
    System.out.println(n); //print after returning from recursion
  }
  //implied base case: do nothing if n <= 0.
}

* Implicit base case
* As you can tell, many ways to do recursion, even for simple examples

Sum 1 - N (iteritive)

public static int sum(int n) {
  int sum = 0;
  for(int i = 1; i <= n; i++) {
    sum += i;
  }
  return sum.
}

Sum 1 - N (recursive)

public static int sum(int n) {
  if(n <= 0) {
    return 0;
  } 
  return sum(n - 1) + n;
}

• What happens if we move the n to directly after the return?

Alternative Sum 1 - N (recursive)

public static int sum(int n) {
  return sum(0, n, 0);
}

private static int sum(int i, int n, int sum) {
  if(i == n) {
    return sum + i; 
  }
  return sum(i + 1, n, sum + i);
}

Generating a String of Numbers

public static void main(String[] args) {
  String str = allDigits(4);
  System.out.println(str);
}

public static String allDigits(int n) {
  if (n <= 0) {
    return "";
  }else {
    return n + " " + allDigits(n - 1);
  }
}

• What does this print?
• How would we reverse the string order?

Reversing a String

public String reverse(String str) {
  if(str.length() == 0) {
    return "";
  }
  if(str.length() == 1) {
    return str;
  }
  return str.substring(str.length() - 1) + reverse(str.substring(0, str.length() - 1));
}

• Sometimes we need multiple base cases

Binary Search

public static int binarySearch(int[] sortedData, int start, int end, int value) {
  // Complete me
}

Lessons Learned

• Recursion -> method calls itself
• Need to break problem down into smaller problems
• Each call creates a copy of that data on the runtime stack
• Need one or more base cases
• Can also do some work on the "way back" from recursive calls