Base vs General Case

Section 21.3 Base vs General Case

Every recursive function will use some kind of selection logic to pick between two cases:

base case 🔗: A case that does not make a recursive call and ends the recursion.
🔗
recursive (general) case 🔗: A case that makes a recursive call, so it adds a new frame to the stack.
🔗

Sometimes, a recursive function will have multiple base cases, and sometimes it will have multiple recursive cases. But it must always have at least one of each.

🔗

We can see this in our countdown function. Lines 2-3 represent our base case. When n == 0, the function stops calling itself:

🔗

Listing 21.3.1. Base case of countdown

🔗

  void countdown(int n) {
    if (n == 0) {
        cout << "Blastoff!" << endl;
    } else {
        cout << n << endl;
        countdown(n - 1); //recursive call
    }
}

We can see this in our countdown function. Lines 4-6 represent our recursive (general) case. When n is not 0, the function continues to call itself:

🔗

Listing 21.3.2. General case of countdown

🔗

  void countdown(int n) {
    if (n == 0) {
        cout << "Blastoff!" << endl;
    } else {
        cout << n << endl;
        countdown(n - 1); //recursive call
    }
}

If there is no base case in a recursive function, or if the base case is never reached, the stack would grow forever—at least in theory. In practice, the size of the stack is limited. If you exceed the limit it is called a stack overflow and your program will crash. In C++, when you do something that accesses memory you should not (like when you overflow the stack), you will encounter a segmentation fault.

🔗

For example, try running this program and then look at the output. Be patient while it runs.

🔗

Listing 21.3.3.

🔗

Since there is no base case, the function does not stop when n == 0. It just keeps on counting! Eventually there is a segmentation fault, which stops the program.

🔗

Insight 21.3.1.

Segmentation fault means “you accessed memory that you should not have.”. One way to do that is a bad pointer. A stack overflow is another way.

🔗

Checkpoint 21.3.1.

Examine the code below. What is the base case?

🔗

void foo(int n) {
  if (n > 100) {
      cout << n << endl;
  } else {
      foo(n * n);
  }
}

n is 0
there is not one
n <= 100
n > 100

🔗

Checkpoint 21.3.2.

🔗

You have attempted of activities on this page.

🔗

Prev Top Next