one thing I was recently thinking about was how a computer finds his variables. When we run a program, the program will create multiple layers in the stack, one layer for every new scope it opens and put either the variable value or a pointer in case of storage in heap in this scope. When the scope is done, it and all its variables will be destroyed. But how does a computer know where its variables are? And which ones to use if the same variables occur to be present more often.
How I imagine it, the computer searches the scope it is in like an array and if it doesn't find the variable it follows the stack downwards like a linked list and searches the next scope like an array.
That leads to the assumption that a global variable is the slowest to use since it has to traverse all the way back to the last scope. So it has a computational time from a * n (a = average amount of variables per scope, n = amount of scopes). If I now assume that my code is recursive and within the recursive function calls on a global variable (let's say I have defined the variable const PI = 3.1416 and I use it in every recursion), then it would traverse it backwards again for every single call and if my recursive function takes 1000 recursion, then it does that 1000 times.
But on the other hand, while learning about recursion, I have never heard that referring to variables that are not found inside the recursive scope is to be avoided if possible. Therefore I wonder if I am right with my thoughts. Can someone please shed some light on the issue.
You got it the other way around: scopes, frames, heaps don't make variables, variables make scopes, frames, heaps.
Both are a bit of a stretch actually but my point is to avoid focusing on the lifetime of a variable (that's what terms like heap and stack really mean) and instead take a look under the hood.
Memory is a form of storage where each cell is assigned a number, the cell is called word and the number is called address.
The set of addresses is called address space, an address space is usually a range of addresses or a union of ranges of addresses.
The compiler assumes the program data will be loaded at a specific address, say X, and that the there is enough memory after X (i.e. X+1, X+2, X+3, ..., all exists) for all the data.
Variables are then laid out sequentially from X onward, it is the job of the compiler to keep the association between the address X+k and the variable instance.
Note that a variable may be instanced more than one time, calling a function twice or recursion are both examples of that.
In the first case, the two instances can share the same address X+k since they are don't overlap in time (by the time the second instance is alive, the first is over).
In the second case, the two instances overlap in time and two addresses must be used.
So we see that it is the lifetime of a variable that affects how the mapping between the variable name and its address (a.k.a. the allocation of the variable) is done.
Two common strategies are:
A stack
We start from an address X+b and allocates new instances at successive addresses X+b+1, X+b+2, etc.
The current address (e.g. X+b+54) is stored somewhere (it is the stack pointer).
When we want to free a variable we set the stack pointer back (e.g. from X+b+54 to X+b+53).
We can see that it's impossible to free a variable that is not the last allocated.
This allows for a very fast allocation/deallocation and naturally fits the need of a function frame that holds the local variables: when a function is invoked the new variables are allocated, when it ends they are removed.
From what we noted above, we see that if f calls g (i.e. f is the parent of g) then the variables of f cannot be deallocated before those of g.
This again naturally fits the semantics of functions.
The heap
This strategy dynamically allocate a variable instance at an address X+o.
The runtime reserves a block of addresses and manages their status (free, occupied), when asked, it can give a free address and mark it occupied.
This is useful to allocate an object whose size depends on the user input, for example.
The heap (static)
Some variables have the lifespan of the program but their size and number is known a compile time.
In this case, the compiler simply assigns each instance a unique address X+i.
They cannot be deallocated, they are loaded in memory in batch along with the program code and stay there until the program is unloaded.
I left behind some details, like the fact that the stack most often than not grows from bigger to lower addresses (so it can be put at the farthest edge of the memory) and that variables occupy more than one address.
Some programming languages, especially interpreted ones, don't associate addresses to variable instances, instead, they keep a map between the variable name (properly qualified) and the variable value, this way the lifespan of a variable can be controlled in many particular ways (see Closure in Javascript).
Global variables are allocated in the static heap, only one instance is present (only one address).
Each recursive function that uses it always references directly to the sole instance because the unique address is known at compile time.
Local variables in a function are allocated in the stack and each invocation of a function (recursive or not) uses a new set of instances (the addresses don't need to be the same each time, but they could).
Simply put, there is no lookup, variables are allocated so that the code can access them once compiler (either relatively, in the stack, or absolutely, in the heap).