Introduction to Recursion

CS 106B: Programming Abstractions

Spring 2022, Stanford University Computer Science Department

Lecturer: Chris Gregg, Head CA: Neel Kishnani

Slide 2

Announcements

• Assignment 2 is due Friday, end of day PDT.
• Add/drop deadline is on Friday – feel free to reach out to the course staff if you have any questions about the class going forward.

Slide 3

A Little Demo

• A Towers of Hanoi puzzle video. The Towers of Hanoi puzzle has three vertical poles, A, B, and C next to each other on a platform. To start, on pole A there are five round discs, one atop another, with the smallest disc (in diameter) on top, and the largest disc on the bottom. The other two poles are empty, but you could put discs on them. The goal of the puzzle is to move all the discs from pole A to pole C, one at a time. You can only move a disc that is on the top of a stack of discs, or on a pole by itself. The catch is that you cannot move a smaller disc onto a larger disc. So, for example, you could move the smallest disc (which is on top) from pole A to pole C in the first move, but you could not move the next largest (which is now on the top of the pole A stack) to pole C next, because it is bigger than the one you already moved to pole C. So, you would have to move the next-larger disc to pole B, and then move the smallest disc also onto pole B (which is okay, because it is smaller than the disc you just moved). Then, you can move the next largest disc from pole A to pole C. Your next move would be to move the smallest disc from pole B to pole A, and then the second largest (at the bottom of pole B) to pole C, and then move the smallest disc from pole A to pole C. At this point, you would have the three smallest discs on pole C. In this manner, you must keep moving discs back and forth without putting a larger disc onto a smaller disc until all the discs are on pole C.

• This can be solved with recursion!
• By the end of today, we will be able to write this program, and you may talk about the algorithm in section

Slide 4

Towers of Hanoi

• Here is the way the game is played (see description above for more specific details):

Slide 5

What is Recursion?

• Recursion is: A problem solving technique in which problems are solved by reducing them to smaller problems of the same form.

Slide 6

Why Recursion?

1. Great style
2. Powerful tool
3. Master of control flow

• We have many simple examples of recursion

Slide 7

Recursion in Programming

• In programming, recursion simply means that a function will call itself:

  int main() {
   main();
   return 0;
  }
  

  (This is a terrible example, and will crash with a "segmentation fault"!)

• main() isn't supposed to call itself, but if we do write this program, what happens?
• We'll get back to programming in a moment!

Slide 8

Recursion in Real Life

(Ridiculously hard puzzle)

• How to solve a jigsaw puzzle recursively ("solve the puzzle")
  • Is the puzzle finished? If so, stop.
  • Find a correct puzzle piece and place it.
  • Solve the puzzle

Slide 9

Counting a column of people

• Let's pretend we have a column of people, one behind the other. Let's try counting the people by only allowing them to ask questions of the people directly behind them and respond to questions to the people directly in front of them. In other words, we have the following rules:
  1. A person can see only the people directly in front and behind them. So, they can't just look back and count.
  2. A person is allowed to ask questions of the person behind them, and respond to the person in front of them.

• How can we solve this problem recursively?

• Answer:
  1. The first person looks behind them, and sees if there is a person there. If there is, they ask them how many people are in line, including them, and wait for a response. If there isn't anyone, the person responds "1", and we are done counting.
  2. If there is a person, that person repeats step 1, and waits for a response.
  3. Once a person receives a response (a number), they add 1 for themself, and they respond to the person that asked them.

Slide 10

Counting a column of people recursively in C++

int numPeopleInLine(Person curr) {
    if (noOneBehind(curr)) {
        return 1;
    } else {
        Person personBehind = curr.getBehind();
        return numPeopleInLine(personBehind) + 1; // recursive call!
    }
}

• Notice that eventually, a person will look behind them and see that there isn't anyone there. That person responds "1", which gets returned to the second-to-last person, who adds 1 to 1, and responds "2". This gets returned to the third-to-last person, who adds 1 to 2, and responds "3". This keeps happening all the way to the first person, who adds "1" and now has a complete count of the number of people in line.

Slide 11

Recursive Structure

• The structure of a recursive function is typically like the following:

  returnValue recursiveFunction(parameter) {
    if (test for simple case) {
       Compute the solution without recursion
    } else {
       Break the problem into a subproblem of the same form, where "parameter" becomes "newParameter"
       Call recursiveFunction(newParameter)
       Get the result of the subproblem, update and return
    }
  }
  

Slide 12

Recursive Functions

• Every recursive algorithm involves at least two cases:
  • base case: The simple case; an occurrence that can be answered directly; the case that recursive calls reduce to.
  • recursive case: a more complex occurrence of the problem that cannot be directly answered, but can be described in terms of smaller occurrences of the same problem.

int numPeopleInLine(Person curr) {
    // base case
    if (noOneBehind(curr)) {
        return 1;
    } else {
        // recursive case
        Person personBehind = curr.getBehind();
        return numPeopleInLine(personBehind) + 1; // recursive call!
    }
}

Slide 13

The Three "Musts" of Recursion

1. Your code must have a case for all valid inputs.
2. You must have a base case that makes not recursive calls.
3. When you make a recursive call it should be to a simpler instance of the same problem, and make forward progress towards the base case.

Slide 14

The "Recursive Leap of Faith"

• You must trust that your recursion will proceed as you have designed it – this is hard to do when you first start coding recursively!

Slide 15

Simple Recursion Examples

• The first real recursion problem we will tackle is a function to raise a number to a power. Specifically, we are going to write a recursive function that takes in a number, x and an exponent, n, and returns the result of x^n.

• When computing a power, we have the simplest case of x^0 = 1.
• We also have a way to define a number raised to a power as a simpler form of itself: x^n = x * x^(n - 1)
• By repeatedly performing the simpler calculation, we will eventually get to a power of 0 (assuming that we have a positive power to begin with), and then we can return our x^0 case of 1.

Slide 16

Let's code power(x, n)

Slide 17

The power(x, n) function

int power(int x, int n) {
    if (n == 0) {
        return 1;
    } else {
        return x * power(x, n - 1);
    }
}

• Each previous call waits for the next call to finish (just like any function):

  int result = power(5, 3);
  

• The first call is to power(5, 3)
  • The second call is to power(5, 2)
    • The third call is to power(5, 1)
      • The fourth call is to power(5, 0), which returns 1.
    • The third call gets the return value of 1, and returns 5 * 1
  • The second call gets the return value of 5, and returns 5 * 5 (25)

• The first call gets the return value of 25, and returns 5 * 25 (125)

• result now holds 125, and this is how recursion works!

• You might argue, wait, I could have done that with a loop just as easily, and you would be right. Recursion isn't always the best way to solve a problem, but we will soon see problems that would be very, very hard to do without recursion (we're looking at simple examples now).

Slide 18

Big O of power(x, n)?

• Guess what? We can apply all of that Big O stuff we just learned to recursive functions, too!
• Let's try and think about how power(x, n) grows as n grows.
• Each time we call the function recursively, we are reducing n by 1. Because we need to go from n all the way to 0, we must call the recursive function n times. Therefore, we have O(n) for our complexity. Neat!

Slide 19

Faster power function!

• An interesting fact about taking a power is that, for even powers, x^n = x^(n/2) * x^(n/2)
• Therefore, if we have an even power, we can calculate x^(n/2) and then just square that when we return…
• We have a special case when n is odd, but this isn't hard to manage.
• Take a look at the following code:

  int power(int x, int n) {
    if(n == 0) {
        // base case
        return 1;
    } else {
        if (n % 2 == 1) {
            // if n is odd
            return x * power(x, n - 1);
        } else {
            // else, if exp is even
            int y = power(x, n / 2);
            return y * y;
        }
    }
  }
  

• We have still made the problem smaller at each recursive call, but we have made it much smaller, by halving it each time.
• What is our complexity?
• O(log n) – wow!

Slide 20

Mystery Recursion: Trace this function

int mystery(int n) {
    if (n < 10) {
        return n;
    } else {
        int a = n / 10;
        int b = n % 10;
        return mystery(a + b);
    }
}

• What is the result of mystery(648)?

  A. 8
  B. 9
  C. 54
  D. 72
  E. 648
  

• First call, mystery(648):

  int mystery(int n) { // 648
    if (n < 10) {
        return n;
    } else {
        int a = n / 10; // a = 64
        int b = n % 10; // b = 8
        return mystery(a + b); // mystery(72)
    }
  }
  

• Second call:

  int mystery(int n) { // 72
    if (n < 10) {
        return n;
    } else {
        int a = n / 10; // a = 7
        int b = n % 10; // b = 2
        return mystery(a + b); // mystery(9)
    }
  }
  

• Third call:

  int mystery(int n) { // 9
    if (n < 10) {
        return n; // return 9
    } else {
        int a = n / 10;
        int b = n % 10;
        return mystery(a + b);
    }
  }
  

• Second and first calls both return the result of the third call (nothing else gets added to the return value), so 9 gets returned all the way to the original calling function.

  A. 8
  B. 9 <---- correct answer
  C. 54
  D. 72
  E. 648
  

Slide 21

More examples! isPalindrome(string s)

• Write a recursive function isPalindrome accepts a string and returns true if it reads the same forwards as backwards.

  isPalindrome("madam");          // true 
  isPalindrome("racecar");        // true 
  isPalindrome("step on no pets") // true 
  isPalindrome("python")          // false 
  isPalindrome("byebye")          // false
  

Slide 22

Remember: The Three "Musts" of Recursion

1. Your code must have a case for all valid inputs.
2. You must have a base case that makes not recursive calls.
3. When you make a recursive call it should be to a simpler instance of the same problem, and make forward progress towards the base case.

Slide 23

isPalindrome

// Returns true if the given string reads the same
// forwards as backwards.
// Trivially true for empty or 1-letter strings.
bool isPalindrome(const string& s) {
    if (s.length() < 2) { // base case
        return true;
    } else if (s[0] != s[s.length() - 1]) { // base case
        return false;
    }
    else { // recursive case
        string middle = s.substr(1, s.length() - 2);
        return isPalindrome(middle);
    }
}

Slide 24

Back to the Towers of Hanoi

• We need to find a very simple case that we can solve directly in order for the recursion to work.
• If the tower has size one, we can just move that single disk from the source to the destination.
• If the tower has more than one, we have to use the auxiliary spindle.
• We can break the entire process down into very simple steps – not necessarily easy to think of steps, but simple ones!

• Let's code the Towers of Hanoi solution!

Slide 25

Recursion Recap

• Break a problem into smaller subproblems of the same form, and call the same function again on that smaller form.
• Super powerful programming tool Not always the perfect choice, but often a good one

• Some beautiful problems are solved recursively

• Three Musts for Recursion:
  • Your code must have a case for all valid inputs
  • You must have a base case that makes no recursive calls
  • When you make a recursive call it should be to a simpler instance and make forward progress towards the base case.