what happens to the stack when a function is called

What Happens When you Call a Function?

What happens under the hood when a part calls some other function?

Firstly, it's important to empathise stack frames. Each function has a stack frame. A stack frame is a "drove of information associated with a subprogram call," (www.cs.uwm.edu). The size and structure of the stack frame varies greatly and is determined at compile time. We call this collection of data a "stack frame" considering nosotros organize each subprogram telephone call in a stack data construction. This means that the first subprogram call (collection of data) that is pushed onto the telephone call stack will be the final stack frame to resolve (terminate). Here'south a step past pace breakup of how the phone call stack is built and how it executes:

1. Any parameters that the part is expecting are pushed onto the stack frame. They're pushed onto the stack frame in reverse society that they were declared in the called functions parameter listing.
2. The return address of the caller function is pushed onto the stack. This will be used to later to return control back to the calling office after the called function has terminated.
3. Now the chosen function is in control. Whatsoever local variables defined inside the called function will be pushed onto the stack as well.
4. Steps i–3 etch what is considered the "stack frame" for the called function. The called function can traverse the stack frame to go whatsoever information that it needs. Now let's examine how the called function returns control to the calling function once it has terminated.

3. Whatever local variables in the chosen function are popped off the stack.

2. The called part returns command to the calling function via the return address of the calling function that we pushed onto the stack.

1. The calling function (in this case not always) is in charge of cleaning up the remainder of the stack — the parameters that the called function was expecting.

0. The chosen office is now in control again. Steps 3–one will be repeated for every bit many stack frames as are created and the stack is clear.

The frame pointer usually denotes the bottom of the stack frame (highest accost because stacks grow up visually towards lower retentiveness). The stack arrow usually denotes the pinnacle of the stack (lowest address). The difference in bytes betwixt the frame pointer and stack arrow is determined by the compiler and represents the size of the stack frame.

The call stack property multiple subroutine calls

Permit'south examine what happens with stack frames in the context of a tricky recursive algorithm problem called "The Ability Sum."

The ability sum problem gives y'all two integers X and N as input. It asks you lot to "Find the number of means that a given integer, 10, can be expressed equally the sum of the powers of unique, natural numbers."

Ex:

X = 100

Northward = 2

We demand to find the number of combinations of unique numbers whose squares sum to 100.

In this case the answer is three:

1. 10² = 100
2. 6² + eight² = 100
3. 1² + 3² + iv² + 5² + 7² = 100

Let'southward run through solving this problem. We'll apply X = 10 and N = 2 to make things more than manageable.

Starting time we demand to accept command-line arguments from the user to become our Ten and Northward. This happens in the primary() function. So we need to call our function p_sum() with three arguments: Ten, N, and num. For our commencement telephone call, num will exist set up to 1. What's the point of num?

Well, nosotros demand to notice all combinations of numbers that, when raised to Northward, equal X. Nosotros will tell our p_sum() function to expect another argument, num, which nosotros will brainstorm raising to the ability North and seeing whether the effect is greater than, equal to, or less than our goal X.

Here is some pseudo-code to hopefully make this more than clear:

1. Take command-line arguments in master() and call p_sum() with 10, N, and num

Note: At present we're in p_sum()

1. Check if pw(num, N) < X

• If num raised to the N is less than X, we can make another recursive call to p_sum() but this fourth dimension with num+i.

jump to instruction #2.

• In the second recursive phone call, nosotros are searching for the number squared that will make up the departure from whatever nosotros generated in the start recursive call minus X. That is, nosotros want to call p_sum() again with (X-pw(num, N), N, num+1).

ii. If pow(num, N) is not less than X, we should bank check if pow(num, N) == Ten. This is a base case and nosotros would return i.

iii. If pow(num, N) is non less than or equal to 10 it must exist greater than X. This is also a base of operations case and nosotros would just return 0.

Permit'southward presume that either base case #2 or #three hit. We will return either 0 or i and terminate the current stack frame. Now we'd need to bound dorsum to the 2nd bullet point and make the side by side recursive phone call in the previous stack frame.

At present allow's have a look at a C implementation of the to a higher place pseudo-code (this code was largely inspired by @sourabhsingh's implementation on HackerRank:

#include <stdio.h>
#include <math.h>
#include <stdlib.h>

int p_sum(int X, int N, int num)
{
if (pow(num, Due north) < X)
return p_sum(Ten, North, num+ane) + p_sum(X-pw(num, North), N, num+1);
else if (pw(num, N) == X)
return 1;
else
return 0;
}

int master(int argc, char* argv[])
{
int X, North, ans;

if (argc < 3)
render 1;

X = atoi(argv[ane]);
N = atoi(argv[2]);

ans = p_sum(X, N, 1);
printf("ans is: %d\n", ans);

return ans;
}

Visual of the phone call stack executing. Offset at frame #0.

My above visual of the call stack executing may appear overwhelming / chaotic. I would strongly recommend tracing information technology out yourself. Python Tutor (can handle many other languages) is also a slap-up resources for visualizing how the stack changes.

Let's briefly run through what'south happening under the hood when nosotros make recursive calls to p_sum() starting in main() at frame #0:

1. The parameters for p_sum() are pushed on to the stack in the reverse order they are listed in the argument list.
2. The return address of the main() function is pushed onto the stack so p_sum() will know where to render control to once it'southward finished executing. Command is now transferred to p_sum().
3. Whatever local variables divers in p_sum() are pushed onto the stack frame.

The same procedure is repeated (with updated values) until the base case is reached and frames brainstorm popping off the stack:

3. Local variables are popped off the stack frame.

2. Command is returned to the previous stack frames and the return address is popped off the stack frame.

1. The parameters used to call the office that has just terminated are popped of the stack frame.

0. The stack frame is now empty and is popped off the stack.

Hopefully you are more enlightened of what's actually happening on the phone call stack when functions are called. This should give you a stronger handle on recursion and make debugging recursive programs easier.

stewartiveresel.blogspot.com

Source: https://medium.datadriveninvestor.com/what-happens-when-you-call-a-function-3ef37f891175

Share this post