CODEWITHSUNDEEP
crecursioncallstack
Thokchom
Thokchom

Reputation: 1652

When we call a function recursively,does it involve a single call stack or one for each invocation of the function?

When in the following code I invoke the function fact() from main(),will this invocation of fact() involve a single call stack for fact() or since fact() is recursive in nature,it will involve a separate call stack for each recursive invocation of fact() that would follow? I am new to recursion and clueless about it. 

#include<stdio.h>

int fact(int);

int main(void)
{
 int a=8;
 printf("The factorial of 8 is %d",fact(a));
}

int fact(int a)
{ 
    if(a==1)
    return 1;
    return a*fact(a-1);
}

Upvotes: 1

Views: 102

Answers (3)

Mats Petersson
Mats Petersson

Reputation: 129474

There is one callstack (unless we deal with threads). It goes from main to whatever the currently last call is. Each call to any function will form a "stackframe" on the stack, which contains the argument(s) to the function, the return address where it goes back to on return and any local variables inside the function.

As mentioned in some answers, there are cases where the compiler will eliminate the recursion as part of it's optimization.

Upvotes: 1

Jans
Jans

Reputation: 11250

Each call to a function preserves the memory space on the stack, so it does not matter if it's a recursive call or not, always have a different space on the stack, to avoid overlaps other state between calls to the other functions.

Upvotes: 0

Basile Starynkevitch
Basile Starynkevitch

Reputation: 1

Compile with all warnings and debugging info (i.e. with gcc -Wall -g on Linux) then use a debugger (gdb on Linux) to step (step command to gdb) and show the backtrace (bt).

There is one single call stack (per thread), but a call stack contains several call frames.

When the machine calls a function, a new stack frame is installed (pushed) on the call stack. When that function returns, the current (topmost) call frame is removed (popped).

Read about call stacks on Wikipedia. Read also about tail calls.

Upvotes: 0

Related Questions