4.8. 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>
#include <cmath>
using namespace std;

void nLines(int n) {
  if (n > 0) {
    cout << endl;
    nLines(n + 1);
  }
}

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

Q-2: 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 isNegative(int n) {
  if (n >= 0) {
    cout << "Not Negative!";
    isNegative(n - 1);
  }
  cout << "Negative!";
}

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

• The function will print "Not Negative!"
• The function will never print "Not Negative!" since we start with a negative number!
• The function will print "Not Negative!" more than once. Then it will print "Negative!" and will stop executing.
• The function will never print "Not Negative!" since we start with a negative number!
• The function will print "Negative!"
• We start with a negative number, so the function will reach the base case.
• The function will never stop executing, there will be infinite recursion.
• We start with a negative number, so the function will reach the base case.

Q-3: isNegative 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 isNegative(int n) {
  if (n >= 0) {
    cout << "Not Negative!";
    isNegative(n - 1);
  }
  cout << "Negative!";
}

int main() {
  isNegative(10);
}

• The function will print "Not Negative!"
• The function will print "Not Negative!", but it won't stop there!
• The function will print "Not Negative!" more than once. Then it will print "Negative!" and will stop executing.
• The function will print "Not Negative!" until it reaches a negative number.
• The function will print "Negative!"
• The function will eventually print "Not Negative!", but that's not all!
• The function will never stop executing, there will be infinite recursion.
• Since we decrement each time, the base case will be reached.

Q-4: The isNegative function has been edited as shown below. What will happen now when we run the code?

#include <iostream>
using namespace std;

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

int main() {
  isNegative(10);
}

• The function will print "Not Negative!"
• The function will print "Not Negative!" but it won't stop there!
• The function will print "Not Negative!" more than once. Then it will print "Negative!" and will stop executing.
• The function will print "Not Negative!" more than once. But will it print "Negative"?
• The function will print "Negative!"
• We start with a positive number, so the function simply won't print "Not Negative!"
• The function will never stop executing, there will be infinite recursion.
• Our input is incremented with every recursive call, so if we start with a positive number, we will never reach the base case.

You have attempted of activities on this page