6.2. Infinite Recursion

In the examples in the previous section, notice that each time the functions get called recursively, the argument gets smaller by one, so eventually it gets to zero. When the argument is zero, the function returns immediately, without making any recursive calls. This case—when the function completes without making a recursive call—is called the base case.

If a recursion never reaches a base case, it will go on making recursive calls forever and the program will never terminate. This is known as infinite recursion, and it is generally not considered a good idea.

In most programming environments, a program with an infinite recursion will not really run forever. Eventually, something will break and the program will report an error.

Warning

Infinite recursion is the first example we have seen of a run-time error (an error that does not appear until you run the program).

You should write a small program that recurses forever and run it to see what happens. Below is an example. The function adds to the number n instead of subtracting, which means it is always larger than 0. Therefore, the function executes "forever." Unfortunately, if there was a snip of live code put in below, the ebook's page would extend down forever because a new line is being created infinitely.

#include <iostream>
using namespace std;

void print_lines(int n) {
  if (n > 0) {
    cout << '\n';
    print_lines(n + 1);
  }
}

int main() {
  void print_lines(10);
}

Q1

If a recursive function never reaches its , then the function will continue executing indefinitely. This is called .

Q2

Take a look at the code below. What will happen if you were to run it on your machine?

#include <iostream>
using namespace std;

void is_negative(int n) {
  if (n >= 0) {
    cout << "Not Negative!";
    is_negative(n - 1);
  }
  cout << "Negative!";
}

int main() {
  is_negative(-10);
}

Q3

is_negative is defined exactly as it was above, but we have changed the call to it in main. What will happen if we run the code with this input?

#include <iostream>
using namespace std;

void is_negative(int n) {
  if (n >= 0) {
    cout << "Not Negative!";
    is_negative(n - 1);
  }
  cout << "Negative!";
}

int main() {
  is_negative(10);
}

Q4

The is_negative function has been edited as shown below. What will happen now when we run the code?

#include <iostream>
using namespace std;

void is_negative(int n) {
  if (n >= 0) {
    cout << "Not Negative!";
    is_negative(n + 1);
  }
  cout << "Negative!";
}

int main() {
  is_negative(10);
}