3 ms·
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 dec
by 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 agoThe 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 agoOr writing a recursive decent parser. Anyone learning recursion needs to write a simple recursive decent parser (say, for evaluating math expressions).