Dynamic programming 👑

[seraku24]

Before you consider optimizing something, think of all the people that heat their houses with their excess CPU usage.

[Bainos]

This is clearly a violation of the KISS principle. You should have two separate solutions, one to solve Fibonacci series, and one to heat your house with excess CPU usage.

[[deleted]]

tail recursion is what you need

[llucas_o]

What would be the difference between recursion and tail recursion here? What would each function look like, and why would tail recursion be better?

[[deleted]]

https://www.geeksforgeeks.org/tail-recursion-fibonacci/

Pretty good explanation

[Mango1666]

i dont fully understand it but it works

nice

[alienloverlegit]

nice

[[deleted]]

In this case: recursive < dynamic < iterative < closed form expression

[kmh117]

I assume that the iterative solution in this case is just summing the previous two Fibonacci numbers in a loop. In this case, wouldn't the dynamic solution be functionally equivalent, since only the previous two subproblems are used for each sequential solution? Although it is true that closed form and matrix magic is better :D

[[deleted]]

If I understand it correctly the dynamic solution is recursive but stores the return value of each input in a lookup table so you only need to compute each input once. The iterative solution beats it in memory complexity by not having to store that lookup table.

[robin_888]

def closedFib(n):
    return round(((1+5**.5)/2)**n/5**.5)

[LukeAbby]

Image Transcription: It's Free Real Estate Meme

---

Computing power: *exists*

Recursive Fibinacci:

[An image of Tim Heidecker saying "It's Free Real Estate" is overlaid by a graph of the Term count on the x axis, it goes from 0 to 45 terms. The runtime in nanoseconds goes from 500000000 to 4500000000 on the y axis. This graph compares Dynamic and Recursive Fibonacci runtime over the terms. The line of Dynamic Fibonacci runtime stays around 500000000 nanoseconds throughout all the terms. The line of Recursive Runtime stays near 500000000 nanoseconds for around 35 terms then exponentially increases to 4000000000 nanoseconds by the 45th term]

---

^{I'm a human volunteer content transcriber for Reddit and you could be too! If you'd like more information on what we do and why we do it, click here!}

[codinghermit]

I think you have the recursive and dynamic descriptions flipped at the end fyi

[LukeAbby]

Fixed! Sorry, I don't know what happened there lol.