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

Question

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 !

Your function doesn't `return` a value when it reaches the `printf`. Probably you should `return o;` instead of printing the value inside `collatz` and print the result in the calling function. — Bodo, May 03 '19 at 12:14
0xC00000FD indicates a stack overflow. Yes, the stack is of finite size. — 500 - Internal Server Error, May 03 '19 at 12:15
included the main() for better understanding of the functionality — Takelovski, May 03 '19 at 12:20
@500-InternalServerError Thanks, although my system is relatively powerful, is the stack static ? meaning does is change in volume from system to system ? — Takelovski, May 03 '19 at 12:24
Actually the stack grows on demand from a preset start size to a preset max size. These sizes are usually defined by the compiler/programmer and recorded in the executable's header. — 500 - Internal Server Error, May 03 '19 at 12:26
By the way: `n==1` not only makes your program flow off the function's end (which initially seems harmless here), but it can trigger very weird UB, as explained in [this post](https://stackoverflow.com/questions/50833352/libboost-resolver-received-sigabrt/50834655#50834655) (just consider the length of the question asked there vs. the actual problem). — andreee, May 03 '19 at 14:12

klutt · Accepted Answer · 2019-05-03T13:10:13.287

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.

Additional note: You can increase the stack size under Linux with [`ulimit -s `](https://linux.die.net/man/3/ulimit) (also possible: `ulimit -s unlimited`) and in MSVC you can set the [`/F `](https://learn.microsoft.com/en-us/cpp/build/reference/f-set-stack-size?view=vs-2019)/[`/STACK:`](https://learn.microsoft.com/en-us/cpp/build/reference/stack?view=vs-2019) compilation flag to increase the stack size of your program. For MinGW, see [this](https://stackoverflow.com/questions/3557691/increase-stack-size-when-compiling-with-mingw) post. — andreee, May 03 '19 at 12:51

score 2 · Answer 2 · edited May 03 '19 at 13:01

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.

edited May 03 '19 at 13:01

klutt

30,332
17
55
95

answered May 03 '19 at 12:21

Blaze

16,736
2
25
44

Nice answer. I improved the formatting a bit. Hope you don't mind. – klutt May 03 '19 at 13:03
@Broman Not at all! Thank you for the fix. I also appreciate your answer that offers the OP a more technical insight. – Blaze May 03 '19 at 13:05

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

2 Answers2