Answering: 'Why does Recursion Take up Space?'

FAANG Coding Interviews / Data Structures and Algorithms / Leetcode

[GregHogg]

Master Data Structures & Algorithms For FREE at AlgoMap.io!

[tacticalmythic]

Not quite. Its actually the call record / function record. Also changes with dynamic vs static scoping rules. But with generic static scoping rules the function call saves certain things, local values, return address, and return values

[xingyuxiang]

Generally speaking, recursions generate the graph, traverse the graph from the bottom to the top, and then delete the graph. Each function call is a node of the graph. Each return value of the function call is the state of that node. How are people going to build this kind of graph without recursions? If people can use an adjacency list, then some DP problems are indeed mediumly hard like using a BFS by a deque. An extra step is to use the clear() method to be aligned with recursions.

For the first few medium questions, either one can use a built-in API from Python that is less familiar or graph building is somewhat straightforward. For example, converting the 1-tree or the singly linked list to a regular list or a bidirectional graph.

[ncmathsadist]

The space you are using is stack frames on the call stack. So you are using plenty of space. The number of frames grows exponentially with the argument.

[PlayBASIC-Developer]

It's just the return address at stored, it's the condition of the register at the time of the call and in languages such as C/C++ the locals are on the stack also.

[augustacybersolutions]

Isn't there a push to not do recursive functions though because of the potential for stack overflow issues which could lead to memory safety problems? I've seen this with NASA guidelines at least.

[RS-fzps]

Superb answer.
Can you make a short about how optimization of tail recursion can be used to “recycle” the stack memory and reuse the same frame to save memory?

[marcelojunior]

As processors don't have unlimited registers, I guess the computed return value from consecutive calls take some memory as well, but I could be wrong tho

[AnshSingh-dkuu]

But every local variable gets popped from the call stack after return statement is called so it shouldn’t take any space at the end right ? Correct me if I am wrong

[chris]

This also assumes no tail recursion optimizations

[syfayre]

explained a concept in a short YT video better than what my teacher did in a full lecture

[seasong]

I guess the compiler could just optimize the recursive functions into a simple sum. Weird how that is not done already.

[juanmacass]

Every parameter and local variable needs memory. In that example besides the address, u have a parameter that needs to be located in memory. Anyway, if you program Fibonacci like that, you have a bigger problem. Execution time will be growing exponentially. That's a very bad solution.

[laughingvampire]

too long, convoluted and unnecessary explanation for "function calls are stored in the stack" stack = memory = space

[FireTruck]

Some of you have never programmed in assembly and it shows