Does recursive functions have some limitations? eg: how many layers does the function require?

3

Made a recursive function which gives how many terms are there in a collatz sequence given a starting number, this is the code n=13 for exemple :

int collatz(long n,long o)
{
    if (n!=1) {
        if(n%2==0)
            return collatz(n/2,o+1);
        else
            return collatz((n*3)+1,o+1);
    } else
        printf("%ld\t",o);
}
void main()
{
    collatz(13,0);
}

the function runs as expected; however with some integers such as "n=113383" something overflows (I guess) and returns :

Process returned -1073741571 (0xC00000FD)   execution time : 4.631 s
Press any key to continue.

Excuse my non technical explanation, many thanks !

c
recursion
stack-overflow
collatz
asked on Stack Overflow May 3, 2019 by Takelovski • edited Sep 25, 2019 by Blaze

2 Answers

3

There is no limitation to recursion depth in the C standard itself. You might cause a stack overflow, but the stack size is different in different environments. I think Windows has 1MB and Linux 8MB. It also depends on the size of the stack frame for the function, which in turn depends on how many variables it has and which type.

In your case, you have two long variables which probably is 8 bytes each. You also have the string "%ld\t" which is 5 bytes, which might end up on the stack, but I'm not sure. On top of that you have the overhead of two pointers to the function return address and to the previous stack frame and they are 8 bytes each on a 64 bit system. So the stack frame for your function will roughly be 32 bytes or so. Maybe a little bit more. So on a Linux system I'd guess that your function would crash at a depth of around 200'000.

If this is a problem, consider rewriting the function to a non-recursive variant. Look at Blaze answer for how that can be done for your case. And as andreee commented below:

Additional note: You can increase the stack size under Linux with ulimit -s (also possible: ulimit -s unlimited) and in MSVC you can set the /F compilation flag to increase the stack size of your program. For MinGW, see this post.

answered on Stack Overflow May 3, 2019 by klutt • edited May 3, 2019 by klutt
2

What happens here is a stack overflow. This happens because every call of the function creates a new stack frame, and if there are too many, the stack's memory runs out. You can fix it by using iteration instead of recursion.

Also, long might not be able to hold the numbers that the collatz sequence produces for a starting value of 113383 (it didn't for me with MSVC). Use long long instead, that is at least 64 bits big. All in all, it could look like this:

void collatz(long long n)
{
    long o;
    for (o = 0; n > 1; o++) {
        if (n % 2 == 0)
            n /= 2;
        else
            n = n * 3 + 1;
    }
    printf("%ld\t", o);
    return;
}

int main()
{
    collatz(113383);
    return 0;
}

Note how instead of recursion we now have a for loop.

answered on Stack Overflow May 3, 2019 by Blaze • edited May 3, 2019 by klutt

User contributions licensed under CC BY-SA 3.0