函数的尾递归

Question

我有一个家庭作业问题，它给出了一个递归函数，我必须使用尾部递归来实现它。函数为f（0）=1
f（n）=1 2*f（n-1）

我并不擅长尾部递归，我试着查找示例，但我发现的都是没有斐波那契序列的示例，这没有多大帮助。

我真正拥有的是

def f(n,s=1):
    if n == 0:
        return s
    else:
        return f(n-1, "i dont know what to put here")

我知道尾递归基本上每次调用都计算函数，我只是不知道如何实现它。
编辑：我打了一个错字f（n）应该是1 2*f（n-1）

Answer 1

对于尾部递归，您可以边走边跟踪总和：

$ cat foo.py 
import sys

def f(n,s=1):
    if n == 0:
        return s
    return f(n-1, 1+2*s)

r = int(sys.argv[1])
print(f(r))

输出：

$ seq 0 10 | xargs -I% python foo.py %
1
3
7
15
31
63
127
255
511
1023
2047