[bogomipz]

>"I'm not sure I know what you mean about stack vs heap not making sense because of Python's memory manager. Will you elaborate?"

In Python everything is an object. Python gives you a reference to that object when you create it. There is no way to tell Python(CPython anyway) in which memory space you would it to create that object.

[dahart]

> There is no way to tell Python(CPython anyway) in which memory space you would it to create that object.

Ah right, that's because all objects are heap-allocated.

You choose heap by using an object for the stack, and rewriting your recursion to use (superficially) iterative code.

You can choose stack allocation instead by using regular recursion: native function calls with local variables.

What you bring up is an interesting issue that can make recursion harder to understand in Python. Having local objects in the stack frame can cause both stack and heap allocation - pointers for the objects on the stack, and the object contents on the heap. Or, you might have global objects that aren't local to the recursive function call or the stack, in which case it's important to understand you're sharing data across function calls.

Generally speaking, you probably don't want individual heap allocations in a recursive function, so it's best not to have local objects. At least performance-wise.

[bogomipz]

>"You choose heap by using an object for the stack, and rewriting recursion using (superficially) iterative code.

You can choose stack allocation instead by using regular recursion: native function calls with local variables."

I'm not following you.

I believe these would both result in the same thing in Python. Python gives you a reference to an object. That object is stored in a private heap "somewhere." That reference to the object that Python gave you is stored on the stack. The object that it points to lives in the heap. This should be the same for both of your examples. I'm not sure what you mean by "native function calls." I am not familiar this this term.

[dahart]

Sorry maybe I’m making it more confusing than it needs to be, I think you do understand the terms.

What we’re talking about is the difference between calling a function recursively (a function that calls itself) and instead simulating recursion using a data structure posing as a stack and an iterative function that doesn’t call itself but instead pushes and pops into your fake stack data structure.

You can either use the system’s built-in stack (by calling functions), or create your own fake stack (by pushing/popping, writing/reading an array, etc.).

Using sys.setrecursionlimit() as mentioned at the very top of this thread only affects the system stack. By “native function calls”, I just mean regular function calls. These are subject to the system’s stack limit.

When you allocate an object and use it as a fake stack to replace the system stack, the size of the object is not subject to the system’s stack limit (which is small — on PCs often a megabyte or two), it’s only limited by the available size of the heap (which is normally large relative to the system stack limit, often gigabytes).

When you make your own fake stack and use an iterative function, you can achieve a much greater recursion depth because your fake stack size is on the heap and not actually in the system stack.

Does that make more sense? The two cases are very different in Python, and using a fake heap-allocated stack, i.e. a Python object, is super useful.

[bogomipz]

I see, yes. It sounds like we are same thing then. Cheers.