8 ms·

The Recursive Book of Recursion

79 points by auraham 2y ago

Willingham 2y ago
- “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 2y ago
  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.
  - MonkeyClub 2y ago
    > gippity This is more my new favorite technical term, I strongly second wider adoption!
analog31 2y ago
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.
- funcDropShadow 2y ago
  Wow, how can you one come up with the impression that induction isn't a problem solving technique and be in a position to decide about math or cs curriculum? Induction is one of the most fundamental proof techniques in mathematics. And every program is isomorphic to a proof in some logic. I'll skip the details, lookup Curry-Howard isomorphism if interested. But that means if you develop a mathematical intuition of induction you also develop an intuition on programs, usually on complicated programs. That is enormously helpful in programming, unless you only want to program CRUD services and spreadsheets.
  - analog31 2y ago
    Ah, you're preaching to the choir. But I'm the only person I know -- in a large technical organization -- who remembers doing proofs in math class and liking it. By the time my kids were in school, proofs had largely vanished from the math curriculum.
deveesh_shetty 2y ago
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 2y ago
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 2y ago
  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 2y ago
    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.
anArbitraryOne 2y ago
[flagged]
- furyofantares 2y ago
  I'm so sorry that happened to you. I hope you're okay.
  - anArbitraryOne 2y ago
    ;)
  - deleted 2y ago
    [deleted]
deleted 2y ago
[deleted]
treebeard901 2y ago
"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 2y ago
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.
- MrVandemar 2y ago
  > why not code them to be run in node Because he considers his readers. I can guarantee that a staggeringly high percentage of the readers have access to a web-browser capable of executing JavaScript (probably 100%). The percentage of the readers with Node installed will be necessarily lower.
retarga 2y ago
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 2y ago
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 2y ago
  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 2y ago
  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.
fire_lake 2y ago
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 2y ago
  > 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 ;)
  - tpoacher 2y ago
    Yep. Especially when a tail recursion can be immediately converted to an equivalent loop by definition (and vice versa). A bizzare comment at best, from someone writing a book on recursion.
- dahart 2y ago
  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_Developing_Safety-Critical_Code 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).
bko 2y ago
As an aside, why is buying from the publisher (the preferred method) almost always more expensive? In this case it's $40 vs $30. Why list it on Amazon for less? Shouldn't the direct from publisher be lower since they don't have to pay Amazon? Plus Amazon throws in free one day shipping. What's the economics behind this?
tpoacher 2y ago
Page 1: For more details, refer to page 1.

79 points by auraham 2y ago

- “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 2y ago
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.
- MonkeyClub 2y ago
  > gippity This is more my new favorite technical term, I strongly second wider adoption!

analog31 2y ago

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.

funcDropShadow 2y ago
Wow, how can you one come up with the impression that induction isn't a problem solving technique and be in a position to decide about math or cs curriculum? Induction is one of the most fundamental proof techniques in mathematics. And every program is isomorphic to a proof in some logic. I'll skip the details, lookup Curry-Howard isomorphism if interested. But that means if you develop a mathematical intuition of induction you also develop an intuition on programs, usually on complicated programs. That is enormously helpful in programming, unless you only want to program CRUD services and spreadsheets.
- analog31 2y ago
  Ah, you're preaching to the choir. But I'm the only person I know -- in a large technical organization -- who remembers doing proofs in math class and liking it. By the time my kids were in school, proofs had largely vanished from the math curriculum.

deveesh_shetty 2y ago

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 2y ago

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 2y ago
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 2y ago
  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.

anArbitraryOne 2y ago

[flagged]

furyofantares 2y ago
I'm so sorry that happened to you. I hope you're okay.
- anArbitraryOne 2y ago
  ;)
- deleted 2y ago
  [deleted]

deleted 2y ago

[deleted]

treebeard901 2y ago

"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 2y ago

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.

MrVandemar 2y ago
> why not code them to be run in node Because he considers his readers. I can guarantee that a staggeringly high percentage of the readers have access to a web-browser capable of executing JavaScript (probably 100%). The percentage of the readers with Node installed will be necessarily lower.

retarga 2y ago

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 2y ago

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 2y ago
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 2y ago
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.

fire_lake 2y ago

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 2y ago
> 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 ;)
- tpoacher 2y ago
  Yep. Especially when a tail recursion can be immediately converted to an equivalent loop by definition (and vice versa). A bizzare comment at best, from someone writing a book on recursion.
dahart 2y ago
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_Developing_Safety-Critical_Code 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).

bko 2y ago

As an aside, why is buying from the publisher (the preferred method) almost always more expensive? In this case it's $40 vs $30. Why list it on Amazon for less? Shouldn't the direct from publisher be lower since they don't have to pay Amazon? Plus Amazon throws in free one day shipping. What's the economics behind this?

tpoacher 2y ago

Page 1: For more details, refer to page 1.