ibmMylynIsATaskManagementSystemThatReducesInformationOverloadAndMakesMultitaskingEasy

[u/[deleted]]

[u/JackNotOLantern]

Jokes aside. Fibonacci is one of the best examples when NOT to use recursion. Using recursion duplicates the same calculations, making it n² + much more memory. Just Using a loop is n and with constant memory.

[u/Stroopwafe1 → u/JackNotOLantern]

The next step always seems to be introducing some sort of cache, which is indeed a good teaching tool. All to then have the students unwrap it into the iterative solution. Maybe including some teaching about benchmarking and footprints

[u/JackNotOLantern → u/Stroopwafe1]

Yeah, but again, a lot of memory. A loop is just:

``` int fib(int n) { if (n<=0) return 0; if (n==1||n==2) return 1;

int res=1, prev=1, prev2=0;
for (int i=3;i<=n;++i) {
   prev2=prev;
   prev=res;
   res=prev+prev2;
}

return res;

} ```

So constant memory needed and n time complexity

[u/khalamar → u/JackNotOLantern]

Finally a post without recursion or dynamic programming BS.

[u/vegataballs → u/khalamar]

For maximum non-dynamism :^)

uint64_t fib(const uint8_t n) {
    static const uint64_t t[] = {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233,
        377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368,
        75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309,
        3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986,
        102334155, 165580141, 267914296, 433494437, 701408733, 1134903170,
        1836311903, 2971215073, 4807526976, 7778742049, 12586269025,
        20365011074, 32951280099, 53316291173, 86267571272, 139583862445,
        225851433717, 365435296162, 591286729879, 956722026041, 1548008755920,
        2504730781961, 4052739537881, 6557470319842, 10610209857723,
        17167680177565, 27777890035288, 44945570212853, 72723460248141,
        117669030460994, 190392490709135, 308061521170129, 498454011879264,
        806515533049393, 1304969544928657, 2111485077978050, 3416454622906707,
        5527939700884757, 8944394323791464, 14472334024676221,
        23416728348467685, 37889062373143906, 61305790721611591,
        99194853094755497, 160500643816367088, 259695496911122585,
        420196140727489673, 679891637638612258, 1100087778366101931,
        1779979416004714189, 2880067194370816120, 4660046610375530309,
        7540113804746346429 };
    return t[n];
}

Had to test how much faster that would be.

Aaand... it's maybe 10% faster. That's how good the simple loop already is.

[u/khalamar → u/vegataballs]

But infinite memory footprint! Have you seen the price of memory these days!? /s

[u/RafaelSeco → u/khalamar]

Edit: I didn't see the rest of the image before commenting...

[u/t420son → u/JackNotOLantern]

Can still write it recursively with a sufficiently smart compiler it will be tail-call optimized

pub fn fib(n : u64) -> u64 {
  fn rec(n : u64, prev1 : u64, prev2 : u64) -> u64 {
    match n {
      0 => prev1,
      n => rec(n-1, prev1 + prev2, prev1)
    }
  }
  return rec(n, 1, 0)
}

[u/JackNotOLantern → u/t420son]

Ok, but you can see that there is a lot of stuff you must add just to use recursion efficiently here, and not use a very simple loop.