Recursion: Moving away from the Base Case

Can we send in a negative number into the parameter of a recursive function, such that it steps further away from the base case with each iteration?

Yes.

What will happen if we do? There are two answers, the practical and the theoretical.

Practical: The program will run for a while, but eventually crash.

With each iteration, we are moving further away from our base case. After some time, the computer will likely run out of memory and segfault.

Theoretical: But what if it didn’t crash?

Here is the code we will be examining:

#include <iostream>
using namespace std;

void recFun(int u)
{
    if (u == 1)
        cout << "Stop!" << endl;
    else
    {
        cout << u << endl;
        recFun(u - 1);
    }
}

int main(void)
{
    recFun(-6);
}

GCC is pretty smart, and if we ask it nicely, it can perform some optimizations that will allow our recursive function to execute without memory consumption growing linearly with each iteration.

The first time I compiled/ran this program, it segfaulted pretty quickly. I compiled again using GCC’s -O3 switch, which gives GCC permission to perform all sorts of (often unsafe) optimizations. This will either avoid or at least postpone the segfault (I can’t claim to have solved the Halting Problem.)

So what can we expect this program to do (assuming it will not crash)?

Well, first it will print -6, followed by -7, but there was never much question about that.

Time for an aside for a very brief Computer Architecture lesson

We know that, at least for our purposes, an int in C++ is a 32-bit number that can be positive or negative. This means an int can hold any integer from -2147483648 to +2147483647. The way it counts is similar to a mechanical odometer, the highest number plus one results in the lowest number and vice versa; it just rolls over.

With this in mind, we can posit that (assuming the program does not crash) the program will eventually print -2147483648, followed by +2147483647, and then continue counting down until it finally prints 2 followed by Stop!

In theory.

This program has been running on my computer for a couple of hours, outputting to a text file.

It has not crashed yet, nor has it finished running. (See: Halting Problem)

If it finishes sucessfully, I would expect the text file to be somewhere around 40GB. I honestly did not expect it would take quite so long to run, so something may have gone awry.

While I was waiting for that program to complete, I made a couple more modifications that illustrate the point on a much smaller scale.

In this version, I declare u a char rather than an int. This means it has a range of -128 to +127.

This version does not require any tricks to run, and we can watch as it counts from -6 down to -128, rolls over to +127 and then finishes counting down as normal.

All of this is to say that, if there is a case where your recursive function is moving further away from the Base Case, something Bad and Wrong has happened.

Depending on what you are trying to do, you might throw an exception if the function receives a negative number when it was expecting a positive number, you might extend the base case to include (u <= 1), or maybe you just shrug and label it Undefined Behavior.

One last aside: As I sit here waiting for the program to terminate, I am reminded of a program that I wrote back in Elementary School in BASIC on a Timex Sinclair 1500. Inspired by a program my dad had written to find prime numbers, my program was designed to “count all the random numbers.”

Not only was the whole idea Bad, but my execution of the idea was Wrong in that I just kept counting random numbers until I saw two in a row that were the same. (Did I mention I was in Elementary School?)

It never finished running, but I don’t think you need to be Alan Turing to figure that out.