[HN Gopher] The Recursive Book of Recursion
___________________________________________________________________
The Recursive Book of Recursion
Author : auraham
Score : 58 points
Date : 2025-01-03 06:43 UTC (1 days ago)
(HTM) web link (inventwithpython.com)
(TXT) w3m dump (inventwithpython.com)
| Willingham wrote:
| - "To understand recursion, you must first understand recursion."
| During the months I've spent writing this book, I can assure you
| that this joke gets funnier the more you hear it.
|
| I love to read books like this rather than the AI generated slush
| that seems to be so abundant today. This author has done a great
| job here. Although I have to say, it is sad that I feel like I
| have to 'audit' everything to see if it's written by a robot
| before I invest too much time in it /:
| rednafi wrote:
| True for blogs as well. The saddest thing is, a few influential
| web folks hqve switched gears to AI evangelism and started
| spamming people with low-quality AI-generated slop. Kinda broke
| the whole circle of trust. Now, if I get the slightest whiff of
| gippity in a text, I just bail out.
| analog31 wrote:
| I first learned about recursion in math class, through the theory
| of induction. Unfortunately, I fear that induction will disappear
| from the math curriculum if it's not seen as a problem solving
| technique.
| deveesh_shetty wrote:
| I remember reading "Automate boring stuffs with Python" it helped
| me a lot while I was in my early college years.
|
| I glanced through the initial chapter of this book, and it is so
| well written even for any newbie to understand.
|
| Personally I have had pretty hard time understanding recursion
| and all the intricacies of it, and still sometimes can't wrap my
| head around it.
|
| Would love to read this book, I have filled the fotm for a review
| to read the free ebook, hopefully i receive a copy!
| voxl wrote:
| Claiming recursion is taught badly and then trying to teach
| recursion immediately via call stacks is certainly a choice. The
| guts of how your favorite compiler implements recursion is hardly
| what I would call "the correct way" to teach the concept.
|
| It's not shocking that students snooze their way through discrete
| math, try their hardest to forget induction proofs, and the
| arrive in algorithms or some other higher level class and try
| their hardest to forget recursion/dynamic programming.
|
| The reality is the concepts are hard and demand practice to
| obtain familiarity. There is no quick path to mathematical
| maturity. If you try your hardest to phone in induction then
| surprise surprise recursion is nonsensical to you.
| theaeolist wrote:
| Recursion is natural and easy to understand when the argument
| of the function is a recursive data structure, and the cases
| are patterns on the constructors. These are natural and useful
| cases, much better than the alternative. Starting with
| misguided examples like factorial is demotivating.
| saghm wrote:
| You're not wrong, but I think there's still something missing
| in terms of how to get from there to a place where people can
| see how (and more importantly, how to recognize _when_) to
| apply the concepts towards what they work on after they've
| learned the basics. In my first semester in college, I took a
| course that was half in OCaml and half in Java. During the
| first half, we used recursion extensively, modeled everything
| via closures rather than objects, and generally learned to
| think about things functionally. Then when we transitioned to
| Java, where we didn't apply any of that and instead used
| objects and for loops and imperative logic. That was the last
| class required for CS majors that used functional
| programming; after that, all of the requirements were either
| Java, C, or didn't use any programming language (but maybe
| used pseudocode, like our algorithms course). I personally
| took a number of other functional language courses as
| electives, like one where we learned Haskell, one about the
| theory of programming languages that used Coq, and a
| compilers course that used OCaml again, and while I wasn't
| the only one, it certainly wasn't a majority who went out of
| their way to take courses like this.
|
| The first time I tried to implement something recursively in
| C++ at my job after college, my more senior teammates were
| concerned about whether we could safely assume that all of
| the different compilers would correctly optimize the tail
| recursion to avoid blowing up the stack, and they preferred
| rewriting the logic to be iterative rather than spend time
| trying to figure that out. This was something I was vaguely
| aware of as a real-world issue, but it hadn't occurred to my
| naive junior engineer mind that I couldn't just assume that
| prestigious "professional" compilers like GCC and Clang and
| MSVC wouldn't take care of this for me when I never had to
| worry about it in OCaml. After all, everyone in the world
| seemed to writing code in C++ with one of these compilers,
| and the OCaml toolchain didn't exactly have a glowing
| reputation in my mind when the only place I had heard of
| using the language didn't even use the default standard
| library!
|
| I'm not saying that I think this is necessarily a good way to
| teach recursion generally, but I definitely think there's
| room for resources like this that help bridge the gap between
| understanding how recursion works in the best possible
| environment for it and showing how it works (warts and all)
| for specific real-world ecosystems.
| plasticchris wrote:
| Call stacks help form a mental model for some people. It's a
| way to help get an initial grip on the topic, one of many.
| Teaching usually involves many simplified models which in my
| experience helps a lot with initial understanding.
| treebeard901 wrote:
| "It is exactly of the same nature as the Hindu's view, that the
| world rested upon an elephant and the elephant rested upon a
| tortoise; and when they said, 'How about the tortoise?' the
| Indian said, 'Suppose we change the subject.' "
| ccapndave wrote:
| Enjoying this so far! One initial comment is that I'm not sure
| the JS examples should all be embedded in an HTML page; why not
| code them to be run in node which means you can scrap the
| `script` tags and use `console.log` which is shorter removes the
| need for including line breaks.
| retarga wrote:
| Yet another Python marketeer. I suggest Lisp or SML to understand
| recursion.
|
| The author was vocal on Reddit defending the suspension of Tim
| Peters. I'm not sure if he ever has contributed anything
| substantial to Python itself. Implicitly defending slander and
| ostracism is vile, so avoid this one.
| dugmartin wrote:
| I think I've posted this here before but the best short
| explanation of recursion I've ever heard was from my programming
| languages professor 35 years ago when we were testing out
| algorithms in a toy Lisp we had to write at the start of the
| course. All non-infinite recursive algorithms should have a "base
| case and a smaller caller", meaning there needs to be a terminal
| state and the algorithm should narrow its scope on each recursive
| call. I still use that to this day when I happen to need to write
| a recursive algorithm.
| jeffrallen wrote:
| This!
|
| Get your base case right and you're 1/n th of the way there.
| Get your recursive calls right and you've got the other (n-2)/n
| th right.
|
| Then you only need to account for the off by one error and
| you're done.
|
| :)
| IIAOPSW wrote:
| This is fine as a beginner rule of thumb but it shouldn't be
| regarded as a universal truth about recursion. Its also
| possible for a simple evaluation without recursion to happen at
| infinity rather than at zero. In practice this usually means
| picking a large value of the input as a cut off point to apply
| an approximation or return a standard value instead.
|
| For example, take an implementation of exp(x). The exponential
| function is defined as the sum to infinity of (x^n)/n!. This
| could be implemented recursively as exp(x,n) =
| 1+(x/n)exp(x,n+1). The challenge is to figure out the value (or
| criteria) for what value of n to cut this infinite evaluation
| short. Well, once n is larger than x all future terms will be
| multiplied by a factor less than 1. So pick some
| proportionality constant k such that if x is k times smaller
| than n (that is, x * k < n) then the remainder is presumed
| negligible and the function returns 1.
|
| Another really nice example I know involves finding the
| resistance across a simple but infinitely repeating circuit. At
| very large n, there are so many resistors in the way that the
| contribution of the remaining circuit connected in parallel is
| basically nothing. So pick whatever value of net resistance R_N
| for an arbitrary cut off point N, then recursively find the net
| resistance in the circuit up to point N-1 connected in parallel
| with everything remaining in the circuit after point N.
|
| There are other cases I can think of where the base case is
| actually the function converging (or becoming linear) for large
| rather than small inputs. And still other cases I know of where
| the function has more than one input argument, and thus it
| might make sense to increase the size in one input to reduce it
| in another etc.
| saghm wrote:
| This sounds a lot like what Coq enforces programmatically to
| avoid any programs that don't terminate from compiling (since
| there's no other looping construct in the language). If I
| remember correctly, languages like this are called "primitive
| recursive", and in some ways I think it's a bit unfortunate
| that we've converged on Turing complete languages as the only
| paradigm used for most real world things; I feel like there's
| untapped potential for making primitive recursive languages
| more ergonomic (like some sort of syntax for "simple" loops
| that can be syntactic sugar for having to manually define a
| recursive function).
| YeGoblynQueenne wrote:
| "Primitive recursive" applies to functions, not languages,
| and -from a practical, programmer's point of view- it refers
| to recursive functions that can be "unrolled" in an iterative
| loop (or just a sequence of repeating steps).
|
| Non-primitive recursive functions are functions that are
| recursive but can't be "unrolled", like the Ackermann
| function (which was specifically created as a demonstration
| that there exist such functions).
|
| Recursion doesn't have to be complicated. It's the syntax of
| most programming languages that makes it complicated. For
| example in Prolog, a clause is recursive if it has a literal
| in the body that has the same symbol and number of arguments
| as in the head literal. This is easy to show with an example:
| head(X,Y):- body(X,Y). head(X,Y):- body(X,Z), head(Z,Y)
|
| That's a recursive predicate. The first clause is not
| recursive- it's the terminating condition. The second clause
| is recursive. The second occurrence of "head(X,Y)" is the
| recursive call.
|
| The only reason you can't do that in Python is because the
| syntax doesn't make it easy. In Prolog a clause is a set of
| literals and a program is a set of clauses so recursion is
| very simple and natural to express as a re-occurring literal
| like I explain above.
| fifilura wrote:
| I would love an example of what you just wrote!
| Jtsummers wrote:
| The simplest example is with factorial. The "base case" is
| when we hit 0 or 1, we want to return 1. By identifying and
| defining this case first you ensure that your program's
| execution will be bounded (which is normally what we want):
| def factorial(n): if n == 0 or n == 1:
| return 1 # recursive case(s)
|
| This is an incomplete program, the next part is to identify
| each of the recursive calls. In this case there's just one,
| and it's achieved by reducing `n` by 1 and multiplying the
| result of the call by the current `n`: def
| factorial(n): if n == 0 or n == 1:
| return 1 return n * factorial(n - 1)
|
| And if you're using a non-braindead interpreter/compiler
| you'd make this more efficient by using tail-calls (these get
| optimized away by reasonable language implementations, the
| main Python implementation is not reasonable):
| def factorial(n, accum=1): if n == 0 or n == 1:
| return accum return factorial(n - 1, accum * n)
|
| For more complex cases, consider a binary tree or node in an
| abstract syntax tree (AST). Assuming an ordered binary tree
| (left node is less than current node, right is greater than
| the current node) and a search over the tree (this is also
| easy to do without recursion at all but for the
| illustration):
|
| Assume the node is something like this:
| @dataclass class Node: item: int = 0
| left: Node = None right: Node = None def
| search(node, value): # 1st base case: the value was
| not found if node is None: return
| False # 2nd base case: the value was found
| if node.item == value: return True
|
| Again, at this point the program is not complete but we've
| identified the two base cases. The next step is to figure out
| the recursive step(s). In this case there are two recursive
| steps but only one will be taken (if we aren't at the base
| cases yet): go left or go right. def
| search(node, value): if node is None:
| return False if node.item == value:
| return True if node.item < value:
| return search(node.left, value) if node.item >
| value: # technically this test will always be
| true if we reach this point # so the right
| search can be made unconditional. I put this here
| # to be more explicit, remove the test to be more efficient.
| return search(node.right, value)
|
| If your data structure or problem has a recursive structure,
| you can use this approach.
| fifilura wrote:
| Thank you! <3
| YeGoblynQueenne wrote:
| >> All non-infinite recursive algorithms should have a "base
| case and a smaller caller", meaning there needs to be a
| terminal state and the algorithm should narrow its scope on
| each recursive call.
|
| Oh, well, I don't like that, sorry. Recursion is a syntactic
| property but what you explain here is an algorithmic one.
| Unbounded recursion, non-terminating recursion and left-
| recursion are still recursion. My intuition is that you should
| teach termination and recursion as different concepts and help
| students understand that they are not the same. So that they
| learn to avoid non-terminating recursion that is.
|
| Btw I think what you describe is called a Knuth-Bendix
| ordering.
| fire_lake wrote:
| I don't understand this book.
|
| It begins by explaining how great recursion is.
|
| Then later it explains why you shouldn't use it for large inputs
| in the two chosen languages (JavaScript and Python) to avoid
| blowing up the stack.
|
| Then it argues that tail call optimisation is bad!
|
| So when is a good time to use recursion?!?
|
| And what is the purpose of the book?
| mrkeen wrote:
| > Then it argues that tail call optimisation is bad!
|
| I didn't think I'd find this, so I went digging. Sure enough:
| The disadvantage of tail recursion is that it requires
| rearranging your recursive function so that the last action is
| returning the recursive call's return value. This can make our
| recursive code even more unreadable. Tail recursive
| functions require rearranging their code to make them suitable
| for the tail call optimization feature of the compiler or
| interpreter. Personally, I take the stance that the
| tail recursion technique should never be used.
|
| What can one do, but just disagree I guess?
|
| > And what is the purpose of the book?
|
| To straw-man functional programming with a one-two punch of "I
| already have that" and "it's bad" so devs never leave Python/JS
| land to find this stuff out for themselves ;)
| dahart wrote:
| Recursion is great for CS education, but recursion should be
| rarely/never used in production code. Tail call recursion is
| one exception to that - I see it in production code
| occasionally. But tail call recursion is limited to cases of
| 1-dimensional recursion that can be transformed into iteration
| - and iteration is better anyway, so even tail calls need some
| extra justification for use in production code.
|
| Check out the famous NASA coding rules. Rule number one is no
| recursion. :P
| https://en.wikipedia.org/wiki/The_Power_of_10:_Rules_for_Dev...
|
| When I was a game programmer, recursion was to be avoided at
| all costs.
|
| Even as a past graphics researcher, I've used recursive flood-
| fill as part of several research papers, and recursive flood-
| fill on a large image will blow your stack, so I _always_
| translate it into a heap allocation and implement recursion
| using an iterative algorithm with breadcrumbs for backtracking.
| It's common for there to be a way to increase the stack size,
| but it's just really annoying and sometimes not possible to
| always be able to do that on any machine you want to run on.
|
| One case where recursion or something that looks like recursion
| is used in production code is when dealing with tree data
| structures. Those are common, and traversing them is common.
| Recursion is acceptable for that - though people who care about
| performance will still optimize it into an iterative algorithm
| whenever possible (which is most of the time).
| YeGoblynQueenne wrote:
| >> Recursion is great for CS education, but recursion should
| be rarely/never used in production code.
|
| How so?
|
| Do you mean "in Python" or similar languages, or do you mean
| in general? I write all my code in Prolog basically and there
| it's all recursion, no iteration. There's no iteration
| constructs. The Prolog interpreter has tail-call optimisation
| and you learn to use it soon enough.
|
| Anyway let's not be all dogmatic like that. Rules always have
| exceptions (including this one ha ha) so there's no point in
| being so absolute about things.
|
| >> Check out the famous NASA coding rules. Rule number one is
| no recursion. :P https://en.wikipedia.org/wiki/The_Power_of_1
| 0:_Rules_for_Dev...
|
| Edit: Rule no 1 from NASA is "avoid complex control flow".
| From your link: 1. Avoid complex flow
| constructs, such as goto and recursion.
|
| Seems that even NASA accepts a modicum of GOTOs and
| recursion.
| mrkeen wrote:
| > Check out the famous NASA coding rules. Rule number one is
| no recursion.
|
| And rule number 3 is no heap allocation.
___________________________________________________________________
(page generated 2025-01-04 23:02 UTC)