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

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