Background

We just saw a lot of function invocations. Go ahead and look at the cost of function invocation. Every function invocation is costly for a program. In the example of recursive functions, we can use neater code, but it comes at a cost. Let’s take a look at it in greater detail.

Introduction to call stack

All programs maintain a “call stack” where every invocation of a function pushes them onto the stack and then removes them when the function returns. Every function invocation adds an execution context of the function to the call stack. This contains the values, variables, and internal information available to that function while execution. The top of the call stack contains the currently executing function’s execution context.

When a function (A) is called from another function (B), this happens:

• The current function (A) is paused while the execution context of the function (A) is maintained within the call stack.

• The function (B) is invoked with a new execution context.

• The execution context of the function (B) is added and maintained on the call stack.

• After function B ends, its execution context is removed. The previous A function is resumed using its execution context which goes at the top of the stack.

The following illustration visualizes this scenario.