Хвостовая рекурсия для функции

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