Recursive dynamic fib

[HyShai]

Is it possible to fix the time complexity of the recursive fib sequence by caching the results? (I don't believe C# uses tail call optimization...)

var n = 9;
var result = RecursiveDynamicFib(n , new int[n+1]);
Assert.AreEqual(result, 34);
public int RecursiveDynamicFib(int finalPos, int[] seq)
{
    if (finalPos < 2) return finalPos;
    return seq[finalPos] != default(int) ? seq[finalPos] : seq[finalPos] = RecursiveDynamicFib(finalPos - 1, seq) + RecursiveDynamicFib(finalPos - 2, seq);
}

Verbose:

public int RecursiveDynamicFib(int finalPos, int[] seq)
{
    var current = 0;
    if (finalPos < 2) current = finalPos;
    else
    {
        if (seq[finalPos] == default(int))
        {
            seq[finalPos] = RecursiveDynamicFib(finalPos - 1, seq) + RecursiveDynamicFib(finalPos - 2, seq);
            current = seq[finalPos];
        }
        else
        {
            current = seq[finalPos];
        }

    }
    return current;
}

[robconery]

Yes - this is one of the things we go over in the video.