【趣味学算法】16_递归练习

注： 本系列仅为个人学习笔记，学习内容为《算法小讲堂》（视频传送门），通俗易懂适合编程入门小白，需要具备python语言基础，本人小白，如内容有误感谢您的批评指正

我们宿舍买了一箱薯片，第一天吃掉了其中一半后又多吃了一包(且不存在吃半包的情况)，第二天照此方法吃完剩下的一半后又多吃一包，每天如此，直到第 10 天早上，发现只剩下一包薯片了。求一共有多少包薯片该怎么实现呢？

我们假设一共有10包：
第一天有10包
第二天吃掉第一天的一半就是5包，然后额外加1包，就是吃了6包，还剩4包 ：4=10 -（10/2+1）
第三天吃掉第二天的一半就是2包，然后额外加1包，就是吃了3包，还剩1包：1=4-（4/2+1）
第四天只剩一包

让将以上过程抽象成数学表达式，剩下的薯片数量$N_{i+1}=N_i-(N_i/2+1)$,$i⩾1$
公式转换一下即可倒过来推每天的初始薯片数量$N_i=2(N_{i+1}+1)$，（到这里是不是觉得很熟悉！没错是数列的记忆在攻击你~）
让我们把数带入看看过程：
第10天：$1$
第9天： $4=2\times (1+1)$
第8天： $6=2\times (4+)1$
第7天： $14=2\times (6+1)$
第6天： $30=2\times (14+1)$
…

以此类推就能倒推出第1天有多少包薯片啦！有了公式我们可以直接用循环实现：

S=1
for i in range(1,10):
    last = 2*(S+1)
    S = last
print(S)

输出结果：

1534

我们发现上述循环其实就是一层层往里套，这熟悉的套娃感，

S=2*(2*(2*(2*(2*(2*(2*(2*(2*(1+1)+1)+1)+1)+1)+1)+1)+1)+1)

这种套娃的形式当然就可以用递归解决啦！代码实现：

#第n天剩下的薯片数
def fun(n):
    if n > 9:
        return 1
    else:
        return 2*(fun(n+1)+1)
    
print(fun(1))

这里可以直观的看出往里套了九层，而fun(1)也算一次调用，所以总共是10次调用，如果想通过代码知道这个递归调用了几次该怎么实现呢

def fun(n):
    global count
    if n > 9:
        count += 1
        return 1
    else:
        count += 1
        return 2*(fun(n+1)+1)

count=0
print(fun(1),count)

输出

1534 10