Comments by "LoneTech" (@0LoneTech) on "Recursion 'Super Power' (in Python) - Computerphile" video.

@jamma246 Having it in the argument name would document it equally well, including for introspection like help(), without writing a separate comment that will get out of sync. The stumbling block in this case is that "from" is a keyword, which frequently leads to ugly names like "from_". By the way, ctrl-p autocompletes in vim.
8
@henrituhola At the point system memory is all used, several systems outright fail in unpredictable ways. It might not even be your process that crashes. You can also run out for distinct reasons such as the stack growing into the address space of another mapping. The recursion limit is a feature, not a bug, simply by virtue of being designed in; it's also adjustable if you're that upset about it. It's certainly possible to have design choices including features with the opposite effects, such as tail call optimization.
6
@framegrace1 There's an obvious point to it; the exception causes a traceback, informing you how you ran into trouble. Remember, Python is designed for beginner programmers to experiment in interactively. Which would you prefer, something to tell you your last entered command had an issue, or suddenly losing all context without warning or explanation?
3
Recursion like this is solving it with a stack. Specifically, it uses the call stack, which in some cases is the only stack available.
2
@Mad_Elf_0 I want to treat it as impossible, because the number of discs is a non-negative integer. It's just not part of the problem domain, and in a statically typed language, shouldn't be a possible call. It's just as helpful as passing a non-numeric object. The problem operates in discrete non-negative integer space and functions correctly if and only if it reaches zero for all its reductions. If your program reaches an impossible state, failing as early as possible (typically, user input validation) helps pinpoint why. In the interest of failing early, it would make sense to assert that the number is a non-negative integer, but it would not help to make a subset of invalid values appear valid. This is like someone telling you to solve the puzzle with nothing but a ball. There are no discs or pegs; you can't perform the task. You're proposing that "I did it!" is the proper response. Adding a successful return of your function when called with bad input is removing the option for the call site to handle the problem, because you never alerted them. This is why "except: pass" is generally a very bad idea; you don't know why there was an exception (or even that there was one or which), and you've removed the opportunity for someone else to interpret it. An example of one that should generally not be silenced, certainly not in a loop, is KeyboardInterrupt - the user has told you to stop, probably for real world reasons your program doesn't understand. PEP 20, the Zen of Python, captures this as "Errors should never pass silently." You should run "import this" from time to time.
2
Quoth the Jargon File: "tail recursion, noun: if you're not sick of it already, see tail recursion"
1
The rules of the towers of Hanoi force discs to always be in order - smallest on top, larger in the bottom. Every function call is moving the largest disc it knows about to a space that has no smaller discs, because it just made a recursive call to move any smaller discs to the third (helper) stack. It finishes by transferring the smaller discs onto the large disc, ensuring that all the smaller discs are on one pillar when the function returns. As long as the deepest call works, and it will because it won't have to move any discs, the whole arrangement of movements will complete the task. Some call designing a function like this "leap of faith" programming; by divide and conquer, we assume we can complete the task for some smaller problem. We then find a set of smallest needed problems to solve, and address those specifically.
1
May I see your easy quicksort using a for loop?
1
@glorytoarstotzka330 Let me provide a clearer example than the quicksort I already mentioned, then. You've surely heard of "mapreduce". That's a contraction of two of the most basic building blocks of functional programming; map and reduce. Map is parallelizable. Reduce also is when using an associative merge operation. That's why they're used for big data. This parallel reduction is a tree based traversal, fundamentally recursive. Essentially recursion is usable for any place you loop, and essential for processing any tree structure, for instance the abstract syntax trees of program compilation. It's possible to move the data of intermediate steps other places than the call stack (some clearly insist it's required), but that's essentially performing another task from FP, the closure. Tail call optimization is when you observe there is no such data so you can remove the intermediate return, and that transforms some recursive loops to iterative loops. Note that these examples do not involve repeated calls; that's a degenerate case (typically exemplified with naïve Fibonacci) frequently shown to promote memoization, an optimization applicable to pure functions.
1
It might save time on a blackboard. In an editor, not so much, and words are both more distinct and descriptive.
1
Spoken like a PLC programmer. Did you notice that recursion is literally one of the four control structures listed at the top of the wikipedia article on structured programming? The logical argument method is called induction, and the call structure of this particular example is a binary tree. The call stack is a usable stack. CPython doesn't inline functions (PyPy might). Understanding recursion, and applying it to problems using inductive reasoning, is the power he refers to. You don't need to spend time reworking a task of this size into machine cycle optimized form; it is far more important that the result be correct.
1
@artit91 You know that's a lie. It's an unmeetable challenge of conspiracy theorist type; you're convinced, even though your own suggestion was the same algorithm (only went "a stack" instead of "the call stack").
1
@artit91 It's an allocated chunk of memory like any other, with limits you can know and adjust. You're just fooling yourself if you imagine heap allocation can't run out. Everything is context dependent and any program that runs is stateful. Asserting an algorithm with O(n) stack requirements, unlikely to be more than 24 bytes per disc, will run out (when we've already demonstrated there's a telling error if it were to happen, that doesn't happen until 1000 deep) is simply premature optimization.
1
@artit91 That's almost fully mistaken. The stack is the simplest, most fundamental form of dynamic memory allocation; it uses one pointer, with one side being free memory and the other occupied. alloca() can therefore just change the stack pointer, relying on the frame pointer to restore it, while functions not using dynamic allocation on the stack (like alloca or dynamically sized automatic arrays) can outright omit the frame pointer. malloc's heap allocation, by contrast, requires tracking at least two pieces of information per chunk of memory; size and if it's free. Added to this is often a heap size which may or may not be dynamic (program break). On top of that it requires the appropriate search algorithms to transfer, split and merge chunks, and will handle fragmentation (when you can't allocate a size that is free, because the free memory is divided by allocated memory). The advantage is that you can free things in arbitrary order. For machines without an MMU, stack placement is trivial; you place static allocations at one end of memory and start the stack pointer at one end of the remaining free space. The heap is frequently statically sized, such that a stack exhaustion is when the stack and heap meet. Often it is assumed that they never will meet, so there's no overhead checking for it, which an MMU would otherwise assist with. The stack is so simple and fundamental it exists even on some computers that don't support indirect memory addressing in the first place, like PIC10. What does typically complicate matters is multithreading, when you need more than one stack. That's why we have calls like pthread_attr_setstacksize, so you can allocate a suitable size for threads depending on their task.
1
@artit91 You're back to repeating your mistaken assumptions. Your "dangerous" line isn't even a proper sentence. Look up the MAP_GROWSDOWN flag sometime.
1
Typing entire words and sentences would help.
1
This is an incorrect generalization. Not all recursive operation is branching; Fibonacci is just the canonical example of where naïve recursion will cause unnecessary complexity, and the forward iterative solution is just as easily written in recursive form: fibfrom a b = a : fibfrom b (a+b)
1
@MadocComadrin Don't forget tge conditions to make the optimization useful and valid: repeated calls and absence of side effects. For instance, our example here prints, which is a side effect.
1
I question this "most languages". It's applicable to any language with subroutine calls having their own name space, which is most. The first two I can think of that don't are early basic (with line number gosub, no blocks or user functions) and ones designed to build statically sized finite state machines (labview perhaps).
1
@CaptainWumbo That makes more sense, though it doesn't change all that much; tail recursive strategies are a subset of recursive strategies, and any other method of tracking allocations is also susceptible to exhaustion. The basics of it is to adapt your methods to data size. I mistakenly read your comment as "can't use recursion" rather than "recursion is limited".
1
But moving a negative stack should fail; it's an impossible action, not lack of action. We could restrict the domain with an explicit test raising a ValueError. This is similar to using a watchdog; the point is to restart your program from a sane state, not keep running in a known broken state.
1
@Mad_Elf_0 Python uses dynamic strong typing, so not really. You could hint it for checkers like MyPy or check at runtime, but the int type is signed. Indeed beyond the scope of the video.
1
@sanderd17 It's less about "against" (though that shows up in weird decisions like moving reduce) than that deep recursion is typically a bug, and tail call optimization means erasing the traceback.
1
But the task is; each of the moves is necessary.
1