Skip to content

Instantly share code, notes, and snippets.

@klmr
Last active September 14, 2022 08:39
Show Gist options
  • Save klmr/301e1eca5aa096fb7cf4d4b7d961ad01 to your computer and use it in GitHub Desktop.
Save klmr/301e1eca5aa096fb7cf4d4b7d961ad01 to your computer and use it in GitHub Desktop.
Efficient, tail recursive fibonacci implementation for R and Python (but since they doesn’t do TCO it’s still using O(n) space)
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 = function (n) {
(\(n, a, b)
if (n == 0L) a
else if (n == 1L) b
else Recall(n - 1L, b, a + b)
)(n, 0L, 1L)
}
@klmr
Copy link
Author

klmr commented Jun 25, 2019

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment