DEV Community


Discussion on: Dynamic Programming Series - Introduction

jvanbruegge profile image
Jan van Brügge

You forgot that C++ has tail call optimization. This means you can run it in constant space:

long Fibbonacci(long n) {
    auto helper = [](long a, long b, long n) { return n > 0 ? helper(b, a+b, n-1) : a; }
    return helper(0, 1, n);
Enter fullscreen mode Exit fullscreen mode

this is similar to the for loop

ankursheel profile image
Ankur Sheel Author

You are right about the tail call optimisation. However, that would have beaten the purpose of gearing this article towards beginners and also keeping it language agnostic. The main issue I have had with other articles (and that I wanted to avoid here) is that either they skip intermediate steps or use tricks which are not conducive to understanding the technique itself.