What is the stack? It's a special region of your computer's memory that stores temporary variables created by each function (including the main() function). The stack is a "LIFO" (last in, first out) data structure, that is managed and optimized by the CPU quite closely. Every time a function declares a new variable, it is "pushed" onto the stack. Then every time a function exits, all of the variables pushed onto the stack by that function, are freed (that is to say, they are deleted). Once a stack variable is freed, that region of memory becomes available for other stack variables.

A key to understanding the stack is the notion that when a function exits, all of its variables are popped off of the stack (and hence lost forever). Thus stack variables are local in nature.

Another feature of the stack to keep in mind, is that there is a limit (varies with OS and varies also with IDE). A lot of online judges set a limit on the memory stack size. So you will see yourself getting Runtime Error when you are declaring a large array into the main, or into some function and exceeding the stack size (Stack overflow). The same situation happens when a recursive function calls itself infinitely.

Example of RE:

int main(){
    int arr[3000][3000];
}

This array's size is nearly 36MB , if you are running your code on a machine with smaller stack size You will get Runtime Error.

Of course not only arrays declared inside functions are stored in the stack, any object (class, struct , STL container).

In Recursion:

Something very important we should consider when writing recursive functions: (if you are not familiar with recursion, refer to this tutorial, Introduction To Recursion). We must think of the maximum number of nested calls. (The maximum depth in the function calls tree).

Let's take this function as an example:

This function generates all numbers made up of n digits and formed by digits 0-9:

 
#include<bits/stdc++.h>
using namespace std;
 
int n;
 
void f(vector < int > v){
 
    if(v.size() == n){
 
        for(int j = 0 ; j < n ; j++)
 
           cout<<v[j];
 
        cout<<endl;
 
        return;
 
    }
 
    for(int dig = 1 ; dig < 10 ; dig++){
 
        v.push_back(dig);
 
        f(v);
 
        v.pop_back();
 
    }
 
}
 
int main(){
    vector < int > v;
    cin>>n;
    f(v);
}
 
 

This function has a total complexity of O(10^n). The memory complexity in this code is O(n^2).

You can notice that at a moment while running the program, there would be n nested calls of the function f :

f(v1)->f(v2)->f(v3)->f(v4)-> ... f(vn)

Where the size of the i-th vector is exactly i. and each vector is a result of appending a digit to the previous one in the hierarchy. So the memory complexity is O(N^2).

All these vectors are stored in the memory stack, once a call is terminated the corresponding vector is popped from the stack and deleted.