Efficient, tail recursive fibonacci implementation for R and Python (but since they doesn’t do TCO it’s still using O(n) space)

fib.py

def fib(n: int) -> int:
    def f(n, a, b):
        if n == 0: return a
        if n == 1: return b
        return f(n - 1, b, a + b)
    
    return f(n, 0, 1)

fib.r

fib = function (n) {
    (\(n, a, b)
        if (n == 0L) a
        else if (n == 1L) b
        else Recall(n - 1L, b, a + b)
    )(n, 0L, 1L)
}

… of course the O(n) space requirement could be lifted by replacing Recall with a trampoline.