A direct recursive Fibonacci implementation is exponential because it recomputes the same values. Memoization makes it O(n), but an iterative solution avoids recursion depth and is simpler. Example: static long Fibonacci(int n) { if (n < 0) throw new ArgumentOutOfRangeException(nameof(n)); checked { long a = 0, b = 1; for (var i = 0; i < n; i++) (a, b) = (b, a + b); return a; } } If recursion is required, pass a dictionary cache. long overflows after F(92), so use BigInteger for larger inputs and validate an upper limit when this is exposed through an API.
Backbencher Developer · · 0 likes