7 ms·

How to Get Better at Recursion

66 points by eatonphil 6y ago

Bootvis 6y ago
See: How to Get Better at Recursion
- tromp 6y ago
  As long as we're making bad jokes, here's another: In order to get better at recursion, you must first understand recursion. In order to get understand recursion, you must first understand recursion. (yes, the lack of a base case makes the joke even worse:-)
- MeinBlutIstBlau 6y ago
  I was hoping it would just have a link that redirected to the question
Naac 6y ago
Could recursion be ( one of ) the reasons why ML and Scheme ( and lisp, clojure, etc. ) aren't popular as industry languages? I learned recursion in University, it's undeniably a foundational piece of Computer Science theory. I use recursion when I have to do interview problems. And I think that's about it. The number of times I actually used recursion in production was maybe twice. And one of those times the PR was rejected. In my experience the overhead of understanding the code outweighs its terseness. This is also how I sometimes feel about macros in clojure. The cons outweigh the pros.
- sokoloff 6y ago
  There are problems that are inherently tree-structured and where anything other than recursion feels wrong. “Process all the files in this directory structure, counting them and summing their size.” Sure, you can solve that without recursing, but I’d trust a recursive algorithm to have fewer hidden bugs.
  - junke 6y ago
    At least the recursive version stops by blowing the control stack when there is a loop in the file system.
- moron4hire 6y ago
  Yeah, every time I've written I recursive algorithm in the past, I've eventually had to come back and reimplement it as iterative. It's such that I no longer start the recursive approach anymore and go straight to iterative. The iterative solution is better in every regard. The state transitions are easier to see, and the sub procedures are easier to identify and split up, if necessary. I have a degree in Computer Science, I did extremely well in that degree program, and I understand algorithms very well. I don't get the fascination with recursion in CS theory. It's just hiding state on the stack frame. That's why it's such a terrible tool, not just for engineering, but for teaching as well. Every recursive solution has an iterative solution, even if it's just tossing your state into a Stack data structure you manage yourself on the heap. You'd think you'd want to call that out for students.
  - dehrmann 6y ago
    I only use recursion where it makes sense and I can guarantee O(log n) runs. Unbalanced tree? Iterate. Large graph? BFS. That said, I agree with another comment here that you're more likely to have a bug code where you're maintaining a stack by hand. Recursion is easier when it's the best fit for the problem.
    - moron4hire 6y ago
      Fundamentally disagree. Any bugs in the iterative approach are likely to be found during development on even the simplest of synthetic test data sets. But the recursive approach has a gigantic bug lying in wait for you to run more data than you originally anticipated: the stack overflow.
      - dehrmann 6y ago
        I used to proctor an on-site laptop coding test where part of the solution involved traversing a large digraph. Maybe 50% of candidates could do it on their own without a bug in 45 minutes. 15% of candidates knocked it out by the halfway mark. Not that this is the best use of recursion--both implementations still need to track visited nodes.
  - 6y ago
- dehrmann 6y ago
  Maybe, but I don't see it as "recursion is hard," I see it as lisps being more clever than pragmatic.
  - Jtsummers 6y ago
    At least Common Lisp, Racket, and Clojure seem more pragmatic than clever to me. How are they "more clever than pragmatic" in your opinion?
- andi999 6y ago
  Probably the other PR just slipped through... What I find difficult with recursion in practice is that the stack depth is quite limited, also depending from what stack depth you are calling the function. Of course memory can also blowup but this is easier to reason (and adding 128gig might just solve it)
  - mrkeen 6y ago
    Stack-depth is an implementation detail. It's chicken-and-egg. Programmers think of recursion as that thing that blows up the stack, so they don't demand that language implementers do a better job with it. Language implementers don't stop recursion from blowing up the stack because no-one is asking them to do so.
    - andi999 6y ago
      Yes. So you cannot use it in production.
- peterkelly 6y ago
  Have you ever - Traversed a directory hierarchy to compute the total size or other statistics about its contents? - Searched for a DOM element on a web page matching certain criteria without using third-party libraries or helper functions like querySelector()? - Implemented a hierarchical navigation structure in a user interface? - Work on parts of a compiler/interpreter or other code that has to deal with formal language? - Written a parser for a file format that contains arbitrarily nested data structures (e.g. HTML/JSON)? - Done anything with trees? - Solved a problem by breaking it down into smaller versions of the same problem, solving those, and then combining the results? I know that for lots of programming tasks recursion is not needed, but I'm genuinely curious as to what kind of software you work on where you've never encountered a problem that requires a recursive solution?
  - vishnugupta 6y ago
    I've been working mostly in the payments domain for the last 16 years. 90% backend, 10% web frontend. So far, I've had write recursive code just once to convert SOAP requests/response to REST request/response on the fly so that the test cases that were written using SOAP client could be reused to test REST end point as well. To state the obvious, the chances of encountering recursive code depends on the domain. In my experience though a typical CRUD business app won't require a recursion as you pointed out. The examples you sited are mostly encountered in a "framework" code (e.g., Spring, some UI framework) and as is typically the case the number of developers "using" a framework is an order of magnitude more than those who implement/maintain them. Same is the case with compiler. On the other hand, those who deal with the lower level system code (OS Kernel, RTOS etc.,) shun recursion altogether to avoid its unpredictable stack need. So in the spectrum of developers the band of coders who frequently deal with or encounter recursion is quite narrow IMO. There are languages where recursion is the only construct available to deal with a collection of values so for those programmers recursive technique is a muscle memory. But I suspect there aren't as many professional users of such languages.
  - lmilcin 6y ago
    None of the above actually require recursion. Some of the above problems have very neat recursive solution but the recursion is bad idea as it tends to various edge cases. For example, "write a parser for a file format that contains arbitarily nested data strucutres", is exactly a problem where you DO NOT want to use recursion, and the reason is that "arbitarily" part. What if there is 1000 levels? What if there is 100 thousand levels? DoS guys love these kinds of implementations. Just send very small, very well compressed payload and look how it all crashes and burns.
- agumonkey 6y ago
  IMO vaguely, lisps and ml are disqualified way earlier. Lisps don't even pass the syntax phase.. newcomers won't have the tool-magic dopamine hook (say the first time you saw PHP map syntax, or ruby blocks or c# interop features). That's what people love at first, it gives a sense of a large new universe of powers.. while lisp is a naked white page of parens.. people just don't see what it's for. Other people will click on the deeper uniformity and lack of syntax as a lever. Same goes for fp.. people see a soup of function, it's meaningless. Again the syntax hook is strong and instead of having f . g . h you get @f.then(g)[[h]] the brain gets tickled differently.
  - kazinator 6y ago
    > newcomers won't have the tool-magic dopamine hook How C wasted the Pascal family languages in the 1980's.
- kazinator 6y ago
  In 2020 I wrote a serialization system for types in C, as the foundation for a kind of distributed database. Types are a tree structure: records with fields that can be records; arrays with elements that can be any type. Thus the serializing and deserializing operations are recursive. The system has no external tooling (no description language). The application uses the C API to construct the needed types at initialization time. I have a test case whereby a whole linked list is serialized and deserialized. The deserialize function mallocs the necessary nodes. There is a function to recursively free the object, using the serial type as a guide. Another time, a little bit farther back, I worked with something recursive on the job fairly recently was speeding up the recursive file system tree walking function in BusyBox. It fails to take advantage of the Linux-specific d_type field in the inode. With that you can avoid stat calls. This shaved a bunch of time off the boot of an embedded system, where BuxyBox's mdev program was scanning through device nodes in /sys. Yet another time. I used recursion to shrink a Linux image by blowing away unused content in the initramfs. That time I used Python to write a kind of "garbage collection" program: it recursively traversed the contents of an initramfs filesystem, determining what files are reachable, marking those files and deleting the rest. Reachability was determined mainly by scanning the file contents for occurrences of the names of other files, with some other heuristics. The root node was the init script; the idea being that anything not required by the initramfs init script is bloat. The idea worked; we got a smaller initramfs that still booted fine.
yinzer-solomon 6y ago
IIRC, “Simply Scheme” describes several different recursion patterns, and it provides a number of exercises that match each pattern.
- eatonphil 6y ago
  Thanks for sharing that! Hadn't heard of it. On my list now.
  - iainctduncan 6y ago
    It's good, and free online, and the authors are both wonderfully generous people.
  - yinzer-solomon 6y ago
    My pleasure. As iainctduncan mentioned, the authors are wonderful teachers, and the book serves as a good warmup before diving into SICP.
barefeg 6y ago
Recursion is a two edge sword. Don’t go rewriting everything recursively if you don’t understand the requirements of the problem in the first place
- DaveSchmindel 6y ago
  Or if you don't know what it entails, RE: space complexity issues within your runtime.
primaryobjects 6y ago
Practicing dynamic programming algorithms is also an excellent way to get better at recursion (and recurrences). Even better, dynamic programming is often more production worthy, since it can result in improved time complexity.
canjobear 6y ago
I took an advanced Scheme programming class in grad school and for a good two years afterwards my code was full of all kinds of fancy recursion, continuation-passing style, monads, etc. I got really good at it. It was a waste of time. Loops are fine.
- deleted 6y ago
  [deleted]
lostmsu 6y ago
Related to the topic, a programming game with really hard recursion puzzles: http://robozzle.com http://robozzle.com
chaabani 6y ago
I think creating a simple programming language that supports recursion is a good way to get better. I did so in one of my side projects that I have recently released as an iOS and macOS puzzle game named "Recursive" where recursion plays a central role and allows solving levels with very short programs [0]. Also, I may be biased, but I think that players can improve their mastery of recursion using the game. If you'd like you can contact me and I will gladly send you a promo code (contact email at website). [0] https://www.kidori.com/games/recursive/ https://www.kidori.com/games/recursive/ (edited to fix typos)
roberto 6y ago
There's some good discussion about the topic here: https://news.ycombinator.com/item?id=26377312 https://news.ycombinator.com/item?id=26377312
- imperistan 6y ago
  Good one :)
peterkelly 6y ago
All the examples are tail recursive, which is exactly equivalent to looping. All you're going to achieve by doing this is to get an inaccurate understanding of what recursion actually is. Practicing working with true recursion would involve algorithms that are not tail-recursive, such as tree traversal. Just read SICP. You can thank me later.
- lmilcin 6y ago
  Still, even when tail recursive it is useful when it ends up with clean code. But then if you want to read it you still have to understand what it is tail recursion and whether it applies in particular case.
  - 8note 6y ago
    A nice thing about tail recursion is having a in interface for what the loop requires at the start. Putting a function call in a loop maybe does that more clearly though
sbrother 6y ago
Easiest way is probably to get a job at a company working a language that forces you to write recursive algorithms. I started my career at a startup where everything was Erlang, and a year of that made FAANG interviews a breeze with all the graph/DP problems.
marshmallow_12 6y ago
how to get better at recursion: see how to get better at recursion. carry on now...
lmilcin 6y ago
I think the best way to master recursion is to think of it as a data structure stored on the actual stack. As you enter you are creating elements (state) and store it on the stack and as you exit you are reducing elements. When thinking this way you can notice a lot of interesting points about recursion. For example, a simple way to test if you can get away with tail recursion is if you can reduce elements as you enter. It means you don't have to store elements as you enter -- no need for data structure on the stack == no need for actual recursion. Another observation to remember is you can write that as an actual stack and implement any recursive problem (for example tree traversal) without recursion. Your data structure contains the state that you need. I would sometimes write recursive solution first and then see if it might be better off rewritten to use a separate stack and loop. Yet another important observation is that on a program stack you don't normally access anything than top of the stack. But for your algorithm having access to all previous levels might be useful. That's where writing it as a separate data structure might be advantageous.
CJefferson 6y ago
The biggest problem with recursion in most languages is the maximum stack size is too small, so you end up banging against the limit when your problem gets big enough. In Rust I'm spinning up another thread just to run recursive algorithms in, which I give a huge (1/2 size physical memory) stack size for running recursive algorithms in.
- souprock 6y ago
  Curious... does Rust require code to be marked unsafe when the maximum depth of recursion can't be proven to fit within the available stack? If not, it's a huge hole in the memory protection.
  - CJefferson 6y ago
    Rust does have code in the compiler to make sure your code "cleanly" segfaults when you stack overflow, so while you can't catch up, you won't (as you do in some other languages) start corrupting the heap, or any other pieces of memory. However, you still can't recover.
    - souprock 6y ago
      That is actually worse than C on Linux. For C, that segfault is provided by the kernel placing a guard page off the end of the stack. C programs recover via sigaltstack, sigaction, and siglongjmp. The C program can continue running safely afterward. I was expecting Rust to give a compile-time error. Rust should refuse to compile a program that would overflow the stack. Unbounded recursion is such a case. Another case would be recursion that is bounded but very large. For example, if the recursion depth can be 128, then on Linux (with the 8 MiB stack default) it would not be allowable to have the stack frames be 64 kilobytes each. That should not compile. Rust is not a memory-safe language.
tmoertel 6y ago
One property that makes recursion attractive is that maps so easily to proof by induction. When designing algorithms, I'll often design a recursive version first, prove it correct, and then translate it into an iterative version. The translation is frequently required to implement the algorithm in common programming languages, most of which have poor support for recursion. For an example, see https://github.com/tmoertel/practice/blob/master/dailycodingproblem_com/p636_find_min_of_rotated_sorted_series_of_distinct_elems.py https://github.com/tmoertel/practice/blob/master/dailycoding...
iainctduncan 6y ago
I'm surprised I get to be the first to say this! But the answer is: work through all the exercises in The Little Schemer. If you actually do this (not just read it!), recursion will be easy and natural by the end of the book. (Or its previous incarnation, The Little Lisper).
- bmitc 6y ago
  I agree with this. I've recently went through the book providing Racket annotations, in the form of implementations and tests, and have the code up in the following repository. Maybe people are interested. https://github.com/bmitc/the-little-schemer https://github.com/bmitc/the-little-schemer I'm about to finish chapter 10, the last chapter and the interpreter section, probably tonight. Another suggestion for getting comfortable with recursion is the Coursera course by Dan Grossman, Programming Languages. https://www.coursera.org/learn/programming-languages https://www.coursera.org/learn/programming-languages
alisonkisk 6y ago
It's pretty easy. Just get better at recursion, until you're good at recursion, then stop.

66 points by eatonphil 6y ago

Bootvis 6y ago

See: How to Get Better at Recursion

tromp 6y ago
As long as we're making bad jokes, here's another: In order to get better at recursion, you must first understand recursion. In order to get understand recursion, you must first understand recursion. (yes, the lack of a base case makes the joke even worse:-)
MeinBlutIstBlau 6y ago
I was hoping it would just have a link that redirected to the question

Naac 6y ago

Could recursion be ( one of ) the reasons why ML and Scheme ( and lisp, clojure, etc. ) aren't popular as industry languages? I learned recursion in University, it's undeniably a foundational piece of Computer Science theory. I use recursion when I have to do interview problems. And I think that's about it. The number of times I actually used recursion in production was maybe twice. And one of those times the PR was rejected. In my experience the overhead of understanding the code outweighs its terseness. This is also how I sometimes feel about macros in clojure. The cons outweigh the pros.

sokoloff 6y ago
There are problems that are inherently tree-structured and where anything other than recursion feels wrong. “Process all the files in this directory structure, counting them and summing their size.” Sure, you can solve that without recursing, but I’d trust a recursive algorithm to have fewer hidden bugs.
- junke 6y ago
  At least the recursive version stops by blowing the control stack when there is a loop in the file system.
moron4hire 6y ago
Yeah, every time I've written I recursive algorithm in the past, I've eventually had to come back and reimplement it as iterative. It's such that I no longer start the recursive approach anymore and go straight to iterative. The iterative solution is better in every regard. The state transitions are easier to see, and the sub procedures are easier to identify and split up, if necessary. I have a degree in Computer Science, I did extremely well in that degree program, and I understand algorithms very well. I don't get the fascination with recursion in CS theory. It's just hiding state on the stack frame. That's why it's such a terrible tool, not just for engineering, but for teaching as well. Every recursive solution has an iterative solution, even if it's just tossing your state into a Stack data structure you manage yourself on the heap. You'd think you'd want to call that out for students.
- dehrmann 6y ago
  I only use recursion where it makes sense and I can guarantee O(log n) runs. Unbalanced tree? Iterate. Large graph? BFS. That said, I agree with another comment here that you're more likely to have a bug code where you're maintaining a stack by hand. Recursion is easier when it's the best fit for the problem.
  - moron4hire 6y ago
    Fundamentally disagree. Any bugs in the iterative approach are likely to be found during development on even the simplest of synthetic test data sets. But the recursive approach has a gigantic bug lying in wait for you to run more data than you originally anticipated: the stack overflow.
    - dehrmann 6y ago
      I used to proctor an on-site laptop coding test where part of the solution involved traversing a large digraph. Maybe 50% of candidates could do it on their own without a bug in 45 minutes. 15% of candidates knocked it out by the halfway mark. Not that this is the best use of recursion--both implementations still need to track visited nodes.
- 6y ago
dehrmann 6y ago
Maybe, but I don't see it as "recursion is hard," I see it as lisps being more clever than pragmatic.
- Jtsummers 6y ago
  At least Common Lisp, Racket, and Clojure seem more pragmatic than clever to me. How are they "more clever than pragmatic" in your opinion?
andi999 6y ago
Probably the other PR just slipped through... What I find difficult with recursion in practice is that the stack depth is quite limited, also depending from what stack depth you are calling the function. Of course memory can also blowup but this is easier to reason (and adding 128gig might just solve it)
- mrkeen 6y ago
  Stack-depth is an implementation detail. It's chicken-and-egg. Programmers think of recursion as that thing that blows up the stack, so they don't demand that language implementers do a better job with it. Language implementers don't stop recursion from blowing up the stack because no-one is asking them to do so.
  - andi999 6y ago
    Yes. So you cannot use it in production.
peterkelly 6y ago
Have you ever - Traversed a directory hierarchy to compute the total size or other statistics about its contents? - Searched for a DOM element on a web page matching certain criteria without using third-party libraries or helper functions like querySelector()? - Implemented a hierarchical navigation structure in a user interface? - Work on parts of a compiler/interpreter or other code that has to deal with formal language? - Written a parser for a file format that contains arbitrarily nested data structures (e.g. HTML/JSON)? - Done anything with trees? - Solved a problem by breaking it down into smaller versions of the same problem, solving those, and then combining the results? I know that for lots of programming tasks recursion is not needed, but I'm genuinely curious as to what kind of software you work on where you've never encountered a problem that requires a recursive solution?
- vishnugupta 6y ago
  I've been working mostly in the payments domain for the last 16 years. 90% backend, 10% web frontend. So far, I've had write recursive code just once to convert SOAP requests/response to REST request/response on the fly so that the test cases that were written using SOAP client could be reused to test REST end point as well. To state the obvious, the chances of encountering recursive code depends on the domain. In my experience though a typical CRUD business app won't require a recursion as you pointed out. The examples you sited are mostly encountered in a "framework" code (e.g., Spring, some UI framework) and as is typically the case the number of developers "using" a framework is an order of magnitude more than those who implement/maintain them. Same is the case with compiler. On the other hand, those who deal with the lower level system code (OS Kernel, RTOS etc.,) shun recursion altogether to avoid its unpredictable stack need. So in the spectrum of developers the band of coders who frequently deal with or encounter recursion is quite narrow IMO. There are languages where recursion is the only construct available to deal with a collection of values so for those programmers recursive technique is a muscle memory. But I suspect there aren't as many professional users of such languages.
- lmilcin 6y ago
  None of the above actually require recursion. Some of the above problems have very neat recursive solution but the recursion is bad idea as it tends to various edge cases. For example, "write a parser for a file format that contains arbitarily nested data strucutres", is exactly a problem where you DO NOT want to use recursion, and the reason is that "arbitarily" part. What if there is 1000 levels? What if there is 100 thousand levels? DoS guys love these kinds of implementations. Just send very small, very well compressed payload and look how it all crashes and burns.
agumonkey 6y ago
IMO vaguely, lisps and ml are disqualified way earlier. Lisps don't even pass the syntax phase.. newcomers won't have the tool-magic dopamine hook (say the first time you saw PHP map syntax, or ruby blocks or c# interop features). That's what people love at first, it gives a sense of a large new universe of powers.. while lisp is a naked white page of parens.. people just don't see what it's for. Other people will click on the deeper uniformity and lack of syntax as a lever. Same goes for fp.. people see a soup of function, it's meaningless. Again the syntax hook is strong and instead of having f . g . h you get @f.then(g)[[h]] the brain gets tickled differently.
- kazinator 6y ago
  > newcomers won't have the tool-magic dopamine hook How C wasted the Pascal family languages in the 1980's.
kazinator 6y ago
In 2020 I wrote a serialization system for types in C, as the foundation for a kind of distributed database. Types are a tree structure: records with fields that can be records; arrays with elements that can be any type. Thus the serializing and deserializing operations are recursive. The system has no external tooling (no description language). The application uses the C API to construct the needed types at initialization time. I have a test case whereby a whole linked list is serialized and deserialized. The deserialize function mallocs the necessary nodes. There is a function to recursively free the object, using the serial type as a guide. Another time, a little bit farther back, I worked with something recursive on the job fairly recently was speeding up the recursive file system tree walking function in BusyBox. It fails to take advantage of the Linux-specific d_type field in the inode. With that you can avoid stat calls. This shaved a bunch of time off the boot of an embedded system, where BuxyBox's mdev program was scanning through device nodes in /sys. Yet another time. I used recursion to shrink a Linux image by blowing away unused content in the initramfs. That time I used Python to write a kind of "garbage collection" program: it recursively traversed the contents of an initramfs filesystem, determining what files are reachable, marking those files and deleting the rest. Reachability was determined mainly by scanning the file contents for occurrences of the names of other files, with some other heuristics. The root node was the init script; the idea being that anything not required by the initramfs init script is bloat. The idea worked; we got a smaller initramfs that still booted fine.

yinzer-solomon 6y ago

IIRC, “Simply Scheme” describes several different recursion patterns, and it provides a number of exercises that match each pattern.

eatonphil 6y ago
Thanks for sharing that! Hadn't heard of it. On my list now.
- iainctduncan 6y ago
  It's good, and free online, and the authors are both wonderfully generous people.
- yinzer-solomon 6y ago
  My pleasure. As iainctduncan mentioned, the authors are wonderful teachers, and the book serves as a good warmup before diving into SICP.

barefeg 6y ago

Recursion is a two edge sword. Don’t go rewriting everything recursively if you don’t understand the requirements of the problem in the first place

DaveSchmindel 6y ago
Or if you don't know what it entails, RE: space complexity issues within your runtime.

primaryobjects 6y ago

Practicing dynamic programming algorithms is also an excellent way to get better at recursion (and recurrences). Even better, dynamic programming is often more production worthy, since it can result in improved time complexity.

canjobear 6y ago

I took an advanced Scheme programming class in grad school and for a good two years afterwards my code was full of all kinds of fancy recursion, continuation-passing style, monads, etc. I got really good at it. It was a waste of time. Loops are fine.

deleted 6y ago
[deleted]

lostmsu 6y ago

Related to the topic, a programming game with really hard recursion puzzles: http://robozzle.com http://robozzle.com

chaabani 6y ago

I think creating a simple programming language that supports recursion is a good way to get better. I did so in one of my side projects that I have recently released as an iOS and macOS puzzle game named "Recursive" where recursion plays a central role and allows solving levels with very short programs [0]. Also, I may be biased, but I think that players can improve their mastery of recursion using the game. If you'd like you can contact me and I will gladly send you a promo code (contact email at website). [0] https://www.kidori.com/games/recursive/ https://www.kidori.com/games/recursive/ (edited to fix typos)

roberto 6y ago

There's some good discussion about the topic here: https://news.ycombinator.com/item?id=26377312 https://news.ycombinator.com/item?id=26377312

imperistan 6y ago
Good one :)

peterkelly 6y ago

All the examples are tail recursive, which is exactly equivalent to looping. All you're going to achieve by doing this is to get an inaccurate understanding of what recursion actually is. Practicing working with true recursion would involve algorithms that are not tail-recursive, such as tree traversal. Just read SICP. You can thank me later.

lmilcin 6y ago
Still, even when tail recursive it is useful when it ends up with clean code. But then if you want to read it you still have to understand what it is tail recursion and whether it applies in particular case.
- 8note 6y ago
  A nice thing about tail recursion is having a in interface for what the loop requires at the start. Putting a function call in a loop maybe does that more clearly though

sbrother 6y ago

Easiest way is probably to get a job at a company working a language that forces you to write recursive algorithms. I started my career at a startup where everything was Erlang, and a year of that made FAANG interviews a breeze with all the graph/DP problems.

marshmallow_12 6y ago

how to get better at recursion: see how to get better at recursion. carry on now...

lmilcin 6y ago

I think the best way to master recursion is to think of it as a data structure stored on the actual stack. As you enter you are creating elements (state) and store it on the stack and as you exit you are reducing elements. When thinking this way you can notice a lot of interesting points about recursion. For example, a simple way to test if you can get away with tail recursion is if you can reduce elements as you enter. It means you don't have to store elements as you enter -- no need for data structure on the stack == no need for actual recursion. Another observation to remember is you can write that as an actual stack and implement any recursive problem (for example tree traversal) without recursion. Your data structure contains the state that you need. I would sometimes write recursive solution first and then see if it might be better off rewritten to use a separate stack and loop. Yet another important observation is that on a program stack you don't normally access anything than top of the stack. But for your algorithm having access to all previous levels might be useful. That's where writing it as a separate data structure might be advantageous.

CJefferson 6y ago

The biggest problem with recursion in most languages is the maximum stack size is too small, so you end up banging against the limit when your problem gets big enough. In Rust I'm spinning up another thread just to run recursive algorithms in, which I give a huge (1/2 size physical memory) stack size for running recursive algorithms in.

souprock 6y ago
Curious... does Rust require code to be marked unsafe when the maximum depth of recursion can't be proven to fit within the available stack? If not, it's a huge hole in the memory protection.
- CJefferson 6y ago
  Rust does have code in the compiler to make sure your code "cleanly" segfaults when you stack overflow, so while you can't catch up, you won't (as you do in some other languages) start corrupting the heap, or any other pieces of memory. However, you still can't recover.
  - souprock 6y ago
    That is actually worse than C on Linux. For C, that segfault is provided by the kernel placing a guard page off the end of the stack. C programs recover via sigaltstack, sigaction, and siglongjmp. The C program can continue running safely afterward. I was expecting Rust to give a compile-time error. Rust should refuse to compile a program that would overflow the stack. Unbounded recursion is such a case. Another case would be recursion that is bounded but very large. For example, if the recursion depth can be 128, then on Linux (with the 8 MiB stack default) it would not be allowable to have the stack frames be 64 kilobytes each. That should not compile. Rust is not a memory-safe language.

tmoertel 6y ago

One property that makes recursion attractive is that maps so easily to proof by induction. When designing algorithms, I'll often design a recursive version first, prove it correct, and then translate it into an iterative version. The translation is frequently required to implement the algorithm in common programming languages, most of which have poor support for recursion. For an example, see https://github.com/tmoertel/practice/blob/master/dailycodingproblem_com/p636_find_min_of_rotated_sorted_series_of_distinct_elems.py https://github.com/tmoertel/practice/blob/master/dailycoding...

iainctduncan 6y ago

I'm surprised I get to be the first to say this! But the answer is: work through all the exercises in The Little Schemer. If you actually do this (not just read it!), recursion will be easy and natural by the end of the book. (Or its previous incarnation, The Little Lisper).

bmitc 6y ago
I agree with this. I've recently went through the book providing Racket annotations, in the form of implementations and tests, and have the code up in the following repository. Maybe people are interested. https://github.com/bmitc/the-little-schemer https://github.com/bmitc/the-little-schemer I'm about to finish chapter 10, the last chapter and the interpreter section, probably tonight. Another suggestion for getting comfortable with recursion is the Coursera course by Dan Grossman, Programming Languages. https://www.coursera.org/learn/programming-languages https://www.coursera.org/learn/programming-languages

alisonkisk 6y ago

It's pretty easy. Just get better at recursion, until you're good at recursion, then stop.