For me, the way to get better at recursion was to be the T.A. of the functional programming class at university and to have to explain it to dozens of confused students during office hours. My main piece of advice was always: stop trying to imagine the flow, you’ll just get lost and more confused. Instead, start with your inductive case: if someone handed you the answer to a smaller problem, how would you get the answer to your problem? Once you’ve figured that out, switch to the base case: what are the smallest problems that you can solve immediately? Put the two together and you’re probably 95% of the way there.
The real way to get better at recursion is to understand the difference between structural and generative recursion, and then understand the relationship between structural recursion and induction.
Every structurally recursive function is a mirror of an inductive definition. The biggest mistake one can make is writing a recursive function without thinking about the inductively defined data it works on.
Does knowing mathematical induction help? It did for me, but not sure if it would help non math folk, though induction is pretty straight forward I’ve always felt.
Knowing induction helps with understanding recursion, but teaching induction to those who don’t have it is one of the harder things. They’re slippery concepts to grasp, for similar reasons.
namely: for everything except the base cases, you make the thing work by assuming the thing already works and using the thing as a component of itself. But you have to shut up the part of your brain that asks “how am I supposed to assume the correctness of f when I haven’t even finished writing it yet? (or, for induction, when that’s the thing I’m supposed to be proving?). It’s kind of like a deferred constraint, everything snaps together in the end, but you have to deal with something that feels wrong when it’s half-finished.
I never really got the understanding of why the usage of recursive functions (instead of loops).
Sure, with proper tail recursion you won’t get stack overflow, but you are still pushing new stack frames for each iteration.
Even if that is not so expensive, staying in the same frame is cheaper.
My limited experience of using debuggers also point to keeping away from recursive functions.
As I understand it, the main downside is that in debugging you don’t see the recursion (because the frames aren’t there
In which case you’re in exactly the same situation as if you’d used iteration, right? If you wrote the code as recursive then you have the option to turn off the tail-call elimination temporarily if it helps your debugging.
Yes, I think the main difficulty more comes in when you have tail calls which are not necessarily recursive (same function), A calls B calls C, all in tail position and you won’t see B on the stack if you break in C.
In that case A, B, and C could all have been labels in the same function, and the calls gotos. That’s what the generated machine code effectively is – which is more efficient than the CPU executing call/return each time.
Yeah, it’s harder to understand in that optimised form. But with optimised tail-calls it’s possible to tell the compiler not to optimise temporarily, if you want.
It can be a fun and interesting puzzle, not something I’d normally do (unless it fit the problem). Also, some languages (such as Erlang, I believe) don’t have loops.
Like someone else already mentioned, there are languages without iteration constructs (Erlang/Elixir are both entirely reliant upon recursion to express iterative constructs like loops, for/foreach, do/while, etc. This is intentional in those languages because there is no support for mutation (there are some ways to work around that, but at the syntax level mutation doesn’t exist), and the runtime provides tail-call optimization, so there is no runtime cost to tail recursive calls, even mutually recursive functions.
On top of that, some algorithms are more elegantly expressed recursively, which can make reading the code much easier to understand. In Erlang/Elixir, which have rich pattern matching capabilities, the ability to break up a function into multiple clauses, each of which pattern match on the function arguments directly in the function head, mean you can neatly express the different cases of a recursive algorithm across a few clauses. For example, in Elixir the following expresses the algorithm for summing a list of integers:
def sum(list) when is_list(list), do: sum(list, 0)
# Base case, empty list
defp sum([], acc), do: acc
# List consisting of at least one element
defp sum([n | rest], acc) when is_integer(n), do: sum(rest, acc + n)
This is obviously a trivial case, but as you can see, each case of the recursive algorithm can be expressed in its own clause, which are pattern matched against the input in top-down order.
There is no difference between tail-recursion and iteration wth respect to debugging. Recursion that is not tail-call optimised gives you more information for debugging than iteration.
The performance of non-TCO can be fine, until it suddenly isn’t. For example, if you don’t control the input you may encounter StackOverflow errors. Last week my team tried to implement a max limit to the number of nodes a tree could have, and one of our test cases was a very, very deep tree that caused a StackOverflow in our initial (naive, non-tail-call optimised) recursive solution.
You actually can, fairly easily. Say your graph has a loop, and you don’t detect that. Try putting the below YAML into http://www.yamllint.com and hit “Go” for example. (Please note I’m not criticising that site in particular. My point is that failing to detect loops is an easy mistake to make: I only had to try 3 online YAML parsers before I found one that doesn’t.)
a: &a [*a]
I don’t know if that site uses a recursive or non-recursive solution, but I’d put good money on some kind of stack overflow happening with that input. And no amount of heap space will help your code avoid a stack overflow (eventually!) if you use the stack to track visited nodes in an infinitely deep tree.
(Edit: extract YAML to its own code block for clarity)
I think you missed the point of my comment: I was trying to give a concrete example of where a TCO recursion would be preferable (performance wise) vs a non-TCO one. You should have used a balanced tree isn’t always an option; especially when the input is user-defined, as I already mentioned it was. As it happens we didn’t really need a stack, as we were only counting nodes to verify the tree didn’t have more nodes than we wanted to allow. And as we’re using lisp, a recursive solution would be the most idiomatic.
You can’t TCO a tree walk – at least not both subtrees.
If you know in advance which subtree is bigger then you can recurse on the smaller one and then TCO on the bigger one, and this limits max stack depth to less than log2(N). But you often don’t know that in advance.
Recursion is easier than iteration.
Iteration makes you think about time and mutation .. do this, and then do this … set this variable to this value, and then later to that value.
With recursion you just say “the answer is this combined with that”.
Iterative sort:
Recursive sort:
the sorted array IS the smallest element, followed by the rest of the array sorted.
the smallest element in an array IS the smaller of the first element and the smallest element in the rest of the array
This seems to explain structural vs generative in a way I ‘get’
Another good resource
That’s termination free iteration, not recursion.
Recursion must have a base case
The base case is “are you bored yet?”
Was about to say this but you beat me to it!
It took me far too long to get this…
Relatedly, I also like this post about recursion.
I’m on to you (ಠ_ಠ)
To get better at recursion, you first have to get better at recursion.
scnr
For me, the way to get better at recursion was to be the T.A. of the functional programming class at university and to have to explain it to dozens of confused students during office hours. My main piece of advice was always: stop trying to imagine the flow, you’ll just get lost and more confused. Instead, start with your inductive case: if someone handed you the answer to a smaller problem, how would you get the answer to your problem? Once you’ve figured that out, switch to the base case: what are the smallest problems that you can solve immediately? Put the two together and you’re probably 95% of the way there.
The real way to get better at recursion is to understand the difference between structural and generative recursion, and then understand the relationship between structural recursion and induction.
Every structurally recursive function is a mirror of an inductive definition. The biggest mistake one can make is writing a recursive function without thinking about the inductively defined data it works on.
Does knowing mathematical induction help? It did for me, but not sure if it would help non math folk, though induction is pretty straight forward I’ve always felt.
Knowing induction helps with understanding recursion, but teaching induction to those who don’t have it is one of the harder things. They’re slippery concepts to grasp, for similar reasons.
namely: for everything except the base cases, you make the thing work by assuming the thing already works and using the thing as a component of itself. But you have to shut up the part of your brain that asks “how am I supposed to assume the correctness of f when I haven’t even finished writing it yet? (or, for induction, when that’s the thing I’m supposed to be proving?). It’s kind of like a deferred constraint, everything snaps together in the end, but you have to deal with something that feels wrong when it’s half-finished.
I never really got the understanding of why the usage of recursive functions (instead of loops). Sure, with proper tail recursion you won’t get stack overflow, but you are still pushing new stack frames for each iteration. Even if that is not so expensive, staying in the same frame is cheaper. My limited experience of using debuggers also point to keeping away from recursive functions.
Isn’t that the point of tail recursion, to re-use the stack frame?
https://en.wikipedia.org/wiki/Tail_call
As I understand it, the main downside is that in debugging you don’t see the recursion (because the frames aren’t there).
In which case you’re in exactly the same situation as if you’d used iteration, right? If you wrote the code as recursive then you have the option to turn off the tail-call elimination temporarily if it helps your debugging.
Yes, I think the main difficulty more comes in when you have tail calls which are not necessarily recursive (same function), A calls B calls C, all in tail position and you won’t see B on the stack if you break in C.
In that case A, B, and C could all have been labels in the same function, and the calls gotos. That’s what the generated machine code effectively is – which is more efficient than the CPU executing call/return each time.
Yeah, it’s harder to understand in that optimised form. But with optimised tail-calls it’s possible to tell the compiler not to optimise temporarily, if you want.
Yet you see the arguments to the call, thus showing you exactly how to replicate your bug without any extra steps
Yes, but see comment above about non-recursive tail calls.
It can be a fun and interesting puzzle, not something I’d normally do (unless it fit the problem). Also, some languages (such as Erlang, I believe) don’t have loops.
Like someone else already mentioned, there are languages without iteration constructs (Erlang/Elixir are both entirely reliant upon recursion to express iterative constructs like loops, for/foreach, do/while, etc. This is intentional in those languages because there is no support for mutation (there are some ways to work around that, but at the syntax level mutation doesn’t exist), and the runtime provides tail-call optimization, so there is no runtime cost to tail recursive calls, even mutually recursive functions.
On top of that, some algorithms are more elegantly expressed recursively, which can make reading the code much easier to understand. In Erlang/Elixir, which have rich pattern matching capabilities, the ability to break up a function into multiple clauses, each of which pattern match on the function arguments directly in the function head, mean you can neatly express the different cases of a recursive algorithm across a few clauses. For example, in Elixir the following expresses the algorithm for summing a list of integers:
This is obviously a trivial case, but as you can see, each case of the recursive algorithm can be expressed in its own clause, which are pattern matched against the input in top-down order.
There is no difference between tail-recursion and iteration wth respect to debugging. Recursion that is not tail-call optimised gives you more information for debugging than iteration.
This sounds like premature optimization. I can’t think of a case when (even non-tail) recursion bit me wrt performance.
The performance of non-TCO can be fine, until it suddenly isn’t. For example, if you don’t control the input you may encounter StackOverflow errors. Last week my team tried to implement a max limit to the number of nodes a tree could have, and one of our test cases was a very, very deep tree that caused a StackOverflow in our initial (naive, non-tail-call optimised) recursive solution.
Your problem is not that you used recursive code, it’s that you used a non-balanced tree.
If you’d used iterative code with a an explicit stack to keep track of your position in the tree you’d have exactly the same problem.
You wouldn’t stack overflow with an explicit stack. Heap size is much larger than the max call stack size.
You actually can, fairly easily. Say your graph has a loop, and you don’t detect that. Try putting the below YAML into http://www.yamllint.com and hit “Go” for example. (Please note I’m not criticising that site in particular. My point is that failing to detect loops is an easy mistake to make: I only had to try 3 online YAML parsers before I found one that doesn’t.)
I don’t know if that site uses a recursive or non-recursive solution, but I’d put good money on some kind of stack overflow happening with that input. And no amount of heap space will help your code avoid a stack overflow (eventually!) if you use the stack to track visited nodes in an infinitely deep tree.
(Edit: extract YAML to its own code block for clarity)
I think you missed the point of my comment: I was trying to give a concrete example of where a TCO recursion would be preferable (performance wise) vs a non-TCO one. You should have used a balanced tree isn’t always an option; especially when the input is user-defined, as I already mentioned it was. As it happens we didn’t really need a stack, as we were only counting nodes to verify the tree didn’t have more nodes than we wanted to allow. And as we’re using lisp, a recursive solution would be the most idiomatic.
You can’t TCO a tree walk – at least not both subtrees.
If you know in advance which subtree is bigger then you can recurse on the smaller one and then TCO on the bigger one, and this limits max stack depth to less than log2(N). But you often don’t know that in advance.
Ah, dang. Thanks for pointing this out.
[Comment removed by author]
I think you meant to post this comment under this story: “Design Patterns” Aren’t
Sure did! Thank you!