[Solved] Stack overflow in recursive function (language C)

Question

You must protect against dividing by zero. Specifically, any time the value of q may be zero. At a minimum you need to test q each time you enter your function. With the additional code you posted, if you insure q isn’t 0 before calling geoprogress, that is sufficient as well. Regardless, a test in geoprogress is a solid failsafe:

int geoprogress (int a, int q, int n)
{
    int result;
    if (n==0)
    {
        result = a;
    }
    if (q == 0)
    {
        return (value of choice);   /* or just return */
    }
    if (n == -1)
    {
        result = geoprogress (a, q, n + 1)/q;
    }
    else
    {
        result = geoprogress (a, q, n - 1)/q;
    }
    return result;
}

You will also need to make sure your function ultimately terminates with n = 0 or in some other way. This makes if (n == -1) look suspicious. What if n = -2? The value of n becomes progressively more negative and the function may never terminate. Without seeing the remainder of the code it is hard to tell, but it looks like if (n == -1) would work better as if (n < 0).

There is also a logic error in the function concerning when/how it terminates. If n > 0, your function enters an endless loop toggling the value of n between 0 and -1:

result: 0  geoprogress (2, 3, 4)
result: 0  geoprogress (2, 3, 3)
result: 0  geoprogress (2, 3, 2)
result: 0  geoprogress (2, 3, 1)
result: 0  geoprogress (2, 3, 0)  /* non-terminating loop entered */
result: 0  geoprogress (2, 3, -1)
result: 0  geoprogress (2, 3, 0)
result: 0  geoprogress (2, 3, -1)
result: 0  geoprogress (2, 3, 0)
result: 0  geoprogress (2, 3, -1)
(snip)

Your test if (n == 0) simply sets result = a and has no control over function return. Your new value of result = a is then immediately overwritten with your next call to result = geoprogress(). It looks like you intended:

if (n==0)
{
    return a;
}

Otherwise, your recursion never terminates because n always bounces around between 0 and -1, neither of which will terminate the recursion. Why? Think about it, look at the following code:

if (n == -1)
{
    result = geoprogress (a, q, n + 1)/q;
}
else
{
    result = geoprogress (a, q, n - 1)/q;
}

Pick any value for n. Now ask yourself when will this return? Answer: It won’t. You either call geoprogress again with n + 1 or geoprogress again with n - 1. You never reach return result in your function. That is what causes me to believe the logic is probably intended to be if (n == 0) return a;. That gives the function a way to return. Either that or one of the other result = needs to be a return.

A recursive function needs at a minimum two things (1) appropriate setup of the values before entering recursion, and (2) a way to return from, or terminate, the recursion. There is virtually no setup in your recursive logic. The only thing you are doing is testing n and increasing or decreasing n by 1. With that being the only setup you provide no way for the recursion to ever terminate as the function is currently written.

Also, you are performing integer division. This makes result = 0 any time geoprogress (...) < q. If you are interested in fractional values, you will need to make result a float or double as well as the type for geoprogress. With the values you provide, the answer is always 3 if you terminate with return a;E.g.:

i: 0  result: 3
i: 1  result: 3
i: 2  result: 3
i: 3  result: 3

What are you modeling and what should the values be? I can continue to look at the function in the abstract, but if I knew what you were modeling, that would really help. Is this representative of some equation or some numerical expansion? Recursion is tricky enough when you have a clear model, recursively modeling the unknown is much more difficult.

After working through the logic of your code once more, what it looks like is missing is an else clause. The recursion works properly as follows (leaving you to prevent q=0, and with the integer div issue)

int geoprogress (int a, int q, int n)
{
    int result = 0;

    if (n==0)
    {
        result = a;
    }
    else
    {
        if (n == -1)
        {
            result = geoprogress (a, q, n + 1)/q;
        }
        else
        {
            result = geoprogress (a, q, n - 1)/q;
        }
    }

    return result;
}

That is your original code with an additional else which was all that was needed to make recursion terminate on (n == 0). Let me know if you have any more questions.

Accepted Answer