Memory Allocation for Recursive Functions

Question

How is memory allocated when recursive functions are called? A function has it's own allocated memory. When it is called, the parameters (not reference-passed ones) and variables get memory. So when the function is called again from within it's body, how is memory allocated to the variables and parameters of the second call?

Solution 1

A recursive function is no different from any other function--automatic local variables are allocated as a single block by advancing the stack pointer far enough to account for the sum of their sizes (plus any padding required for alignment).

Each recursive call pushes a new stack frame in that manner, then pops it when it returns. If the recursion fails to reach a base case, the stack will rapidly be exhausted leading to the eponymous Stack Overflow crash.

Solution 2

Calling a function recursively is done just like any other function. So the memory will be allocated the same way as if you are calling any regular function.

Solution 3

When a function (call if func1) calls another function (call it func2), the data necessary for execution of func2 is pushed on to the stack. That does not change for recursive functions (when func2 is the same as func1).

If a recursive function gets called 10 times recursively, there will 10 stack frames, each corresponding to one invocation of the function.

Solution 4

The Recurtion uses Stack memory to get executed

Go through the below example

void rev(Node* head){
if(head==NULL) return;
head=head->next;
rev(head);
cout<<head->data<<endl;}

Lets have a look in Stack Segment for recursion.

Let NODE1 -> NODE2->NULL Where NODE1 and NODE2 are struct objects.

What your function doing is:

Call to rev(NODE1)
Check if it is NULL
Point to next NODE i.e. NODE2

Call to rev(NODE2)

Check if It is NULL
Point to next NODE i.e. NULL

Call to rev(NULL)

Check if It is NULL
Pointer will be returned With head = NULL

Hope this will Help you.

Solution 5

Function parameters and local variables are allocated on the stack. They form a so-called stack frame. When a function is called recursively, a stack frame is allocated for each of the recursive call of the function.

E.g. if void f() is recursively called three times.

// Assume stack grows upwards
stack frame #3 <== the most recent call
stack frame #2
stack frame #1

View more solutions

Comments

[Caesar]

C++ does NOT guarantee that the automatically managed memory will be allocated on a stack like structure.

[Caesar]

C++ does NOT guarantee that the automatically managed memory will be allocated on a stack like structure.

[brokenfoot]

Like I said, the recursive function is treated like any other function, which is allocated on stack. If you'll look into the assembly, there will be a PUSH & POP operation. That has to be on a stack only. btw what do you mean by ` automatically managed memory` ?

[Eric Z]

I think it's de facto when recursion function is used. Why wouldn't it in this case?

[Drew Hall]

@Caesar: While it's true that the C++ standard does not use the word "stack" for this, the specified semantics of "automatic storage duration" and the mechanics of every major processor instruction set architecture (ISA) all but guarantee a stack will be used.

[Caesar]

While most automatically managed memory is handled using a stack, C++ does not guarantee that all systems must use a stack to store the memory.

[brokenfoot]

I agree with your point there. But it is applicable for variables in a function. I think the discussion here is about the function stack. Although a variable might be allocated on a register but when another function is called, that variable has to be stored onto the stack, otherwise register is just a temporary placeholder, which the next function may use. Hence if the variable is stored on in a register, it has to be located on the function stackframe to preserve the value across function calls.

[Drew Hall]

@Caesar: Because it's essentially a non-answer. You're correct that it's the same as any other type of function, but you stop short of explaining what that actually means.

[Caesar]

@DrewHall It answers the question, if he needs to know how a regular function allocates memory then that is another question entirely.

[Drew Hall]

@Caesar: Perhaps. But I think inherent in the question is a lack of understanding of the mechanics of the call stack.