3

My concern is about what will use stack memory in an instruction involving arithmetics and a recursive function call such as:

return 5 + f(a-1); //f is recursive

I'd like to understand what is put on the stack, and when, so that I know what could or couldn't cause memory issues in case of a deep recursion. Here is a more complete example:

int f(int a) {
    if (a > 0) {
        return 5 + f(a-1);
    }
    else {
        return 0;
    }
}

Let's focus on the line return 5 + f(a-1); What will we have to store in memory around that point?

  • We do have a place in the stack for the integer a since the variable is local to f
  • will the values 5 and 1 be stored?
  • what about the result of the operation a-1, will it be put on the stack?
  • what about the return value of f?

The "worst case" scenario regarding the amount of memory used would be that at some point all of these will be on the stack at the same time. A better case would be that there will be allocations and deallocations in sequence such that not everything is kept in memory.

How will it happen? Is it up to the compiler?

Many thanks,

Guillaume Chérel
  • 1,478
  • 8
  • 17

4 Answers4

3

If it stays recursive, you'll have to have space on the stack for at least a stack frame (eg, previous stack pointer or equivalent register for maintaining stack frames, return address and space for return value) and the a-1 variable being passed in. The 5 and the 1 almost certainly wouldn't go on the stack, they'd be hard-coded within the code most likely.

That may not seem like much but, if you call f(999999999), you're going to kill your stack. Recursion's not that suited for a-1-type operations.

However, your compiler may be smart enough to do tail-end recursion optimisation on something like this:

int f(int a) {
    if (a <= 0) return 0;
    return 5 + f(a-1);
}

Of course, I'm assuming that that code you is just a sample since I think it could probably be replaced with the non-recursive and even non-iterative:

int f(int a) { return (a > 0) ? a * 5 : 0; }

:-)

paxdiablo
  • 854,327
  • 234
  • 1,573
  • 1,953
  • 2
    If the downvoter would care to point out _why_ this answer is not useful, I could think about fixing it. But I'm pretty certain there's nothing wrong with it myself. – paxdiablo Jan 27 '11 at 12:31
  • Does "if it stays recursive" mean "if your compiler doesn't optimize your code into a non recursive way"? (and yes, it is just a sample meant only to be illustrative and simple) – Guillaume Chérel Jan 27 '11 at 12:55
  • Could you briefly state what sp/bp stands for? – Guillaume Chérel Jan 27 '11 at 12:56
  • 1
    Yes, gcc (for example) has optimisations that have kept me entertained for days trying to figure them out. I _do_ mean "if the compiler leaves it (unoptimised) as recursive". And sp/bp are the stack pointer and base pointer, two x86 registers. Stack frames are typically built by saving the last stack pointer on the stack so you can recover the last frame easily. Obviously, that's architecture-specific. – paxdiablo Jan 27 '11 at 12:56
  • "sp" is an universal acronym for stack pointer, used by every kind of CPU I've ever seen. As for "bp", since the original poster never mentioned using x86, I'll assume it means British Petrolium. – Lundin Jan 27 '11 at 13:11
2

"Stack" in this context could as well be internal CPU registers / cache, depending on CPU and compiler. I'll call them all stack to keep things simple.

The things that are stored on the stack per function call are: - The variable a. - The returned value. - The return address of the caller. - Possible the "condition code register" or equivalent fundamental CPU register, depending on the architecture. Possibly the program counter etc as well. I.e the static overhead you get each time when calling a function.

The expression

return 5 + f(a-1);

The 5 is a constant that will be stored in program memory and doesn't affect the stack. The -1 will most likely be transformed into the assembler instruction "decrease by one", and thus end up in program memory as well.

The result of the expression a-1 will be stored on the stack and the result will become the "new a" for next recursion.

To sum this up, the big culprit in this case isn't really the variables you showel back and forth on the stack, but the stack space needed for the function call overhead itself.

Lundin
  • 195,001
  • 40
  • 254
  • 396
0

Take a look at this site about C Function Call Conventions and the Stack

Also, if you're worring about stack overflows and your compiler is not able to optimize tail recursion, you can transform your code to a non-recursive alternative by transforming tail into a while loop, or in the case of non tail recursive functions you should be able to create and manage a stack data-structure by yourself (see Way to go from recursion to iteration)

God bless!

Community
  • 1
  • 1
Trinidad
  • 2,756
  • 2
  • 25
  • 43
-3

As far as I understand, this is what will happen:

  • a must be placed on the stack because it's a local variable.
  • Naturally the parameter to f must be placed on the stack.
  • The value 5 should be placed on the stack because it needs to be saved for the later + operation.
  • If I remember correctly, the return value is treated like a parameter, so it will be placed on the stack too.
  • And of course the instruction pointer.

But maybe the complier does some optimizations I'm not aware of.

Ilya Kogan
  • 21,995
  • 15
  • 85
  • 141