C Recursion & Memory

Question

How does the computer saves each changed 'i' value in the memory and prints them out?
How many bytes are being used in this code? 24 bytes (i = 5, 4, 3, 2, 1, 0) or only 4 bytes?

Following code prints: 1, 2, 3, 4, 5.

#include <stdio.h>

void test(int i)
{
    if (i == 0) return;
    test(i - 1);
    printf("%d\n", i);
}

int main(void)
{
    test(5);
    return 0;
}

First you need to understand what a stack is. Next you need to realize that your question is *unanswerable* without a number of details of the system and compiler. — Chris Stratton, Oct 16 '19 at 23:45
Try reading this excellent explanation of recursion: https://stackoverflow.com/a/37010/1212725 — bruceg, Oct 16 '19 at 23:48
@Barmar I agree, but the answer bruce linked shows recursion visually quite nicely — Jeeter, Oct 17 '19 at 00:27

score 2 · Answer 1 · answered Oct 17 '19 at 02:27

The 'stack' on modern CPU architectures is a region of memory (separate for each thread) that stores, among other things, the return address when a function call is made, function call parameters, non-static local variables (typically in that order, but not always). Every time any function is called in C (and most modern languages), the return address (the address to jump to once the function about to be called finishes execution) is pushed onto the stack, and the stack pointer is incremented by the size of an address (assuming the stack grows up), then each function parameter is pushed onto the stack, and the stack pointer is again incremented by the size of each parameter. As each function local variable is allocated space, the stack pointer is incremented by the size of that variable as it is pushed onto the stack. When the function returns, the stack pointer is 'unwound' by the value of the size of each variable that was pushed onto the stack, as they are popped off of the stack. Next the function call parameters are popped from the stack, and again, the stack pointer is decremented by the size of each parameter. Finally, the function jumps to the return address that was originally pushed to the stack when the function was called, and it is popped, and the stack pointer is decremented by the size of an address. We are now ready to execute whatever code comes after the function call, and the stack pointer is right back where it was before the function call.

In the case of recursive function calls, the return address, function call parameters, and function local variables are pushed onto the stack for each nested function call, but are not popped from the stack until the final recursive function call returns. They are popped off the stack in the opposite order they were pushed onto the stack (as stacks are by nature Last In First Out, LIFO, data structures).

Assuming this is executing on a 32bit CPU, and an 'int' is 4 bytes, then the return address for each recursive function call, plus the one function parameter would get pushed onto the stack. At the greatest stack utilization, immediately before test(0) returns, we would have 6x recursive calls (for 5,4,3,2,1,0), and a 32 bit (4 byte) return address, plus a 4 byte parameter for each call, so 6 * (4 + 4) = 48 bytes.

score 1 · Answer 2 · answered Oct 17 '19 at 00:21

Each instance of test gets its own instance of i. When you call a function, the current execution environment of the current function is stored and the context is set up for the new function. When that new function returns, the context of the calling function is restored.

C Recursion & Memory

2 Answers2