6 ms·

Practice makes perfect, I think most learners can get comfortable with recursion as they use it to implement simple recursive solutions (Fibonacci, tree travers

by Edmond 9y ago

Practice makes perfect, I think most learners can get comfortable with recursion as they use it to implement simple recursive solutions (Fibonacci, tree traversals..etc). Over time it becomes quite natural to recognize when and how to use recursion. One source of confusion that most learners have stems from the seemingly mysterious way that intermediate results are kept track of. This is one of the downsides of not having experience with low-level programming. If you're familiar with assembly language programming and understand how register contents are pushed/poped on/off the stack between sub-routine calls then it is easier to understand what is happening behind the scenes.

projektir 9y ago
> If you're familiar with assembly language programming and understand how register contents are pushed/poped on/off the stack between sub-routine calls then it is easier to understand what is happening behind the scenes. Assembly programming in college is exactly what made recursion really click for me!
- khedoros1 9y ago
  I taught myself to be comfortable writing recursion through practice, practice, and practice, but I feel like things clicked at an entirely different level when I could trace something in assembly and see that the arguments were actually being stored in different locations as the stack pointer increased.
roywiggins 9y ago
Of course, Fibonacci is kind of an awful example, since the naive recursive solution is O(n^2) and besides it's much easier to implement iteratively. It's a decent toy problem, but it makes me worry that it gives people the wrong idea.
- eru 9y ago
  The naive Fibonacci takes O(fibonacci(n)), which is exponential. Roughly O(1.62^n). Not merely quadratic. I think a good example of (mutual) recursion that actually makes sense is eg implementing some state machines.
  - chii 9y ago
    Or writing a recursive decent parser. Anyone learning recursion needs to write a simple recursive decent parser (say, for evaluating math expressions).

by Edmond 9y ago

projektir 9y ago

> If you're familiar with assembly language programming and understand how register contents are pushed/poped on/off the stack between sub-routine calls then it is easier to understand what is happening behind the scenes. Assembly programming in college is exactly what made recursion really click for me!

khedoros1 9y ago
I taught myself to be comfortable writing recursion through practice, practice, and practice, but I feel like things clicked at an entirely different level when I could trace something in assembly and see that the arguments were actually being stored in different locations as the stack pointer increased.

roywiggins 9y ago

Of course, Fibonacci is kind of an awful example, since the naive recursive solution is O(n^2) and besides it's much easier to implement iteratively. It's a decent toy problem, but it makes me worry that it gives people the wrong idea.

eru 9y ago
The naive Fibonacci takes O(fibonacci(n)), which is exponential. Roughly O(1.62^n). Not merely quadratic. I think a good example of (mutual) recursion that actually makes sense is eg implementing some state machines.
- chii 9y ago
  Or writing a recursive decent parser. Anyone learning recursion needs to write a simple recursive decent parser (say, for evaluating math expressions).