递归学习：台阶问题+python代码

递归学习：台阶问题+python代码"/>

递归学习：台阶问题+python代码

问题介绍：

1. 假设一段楼梯共n个台阶，小明一步最多能上3 个台阶，编写递归函数计算小明上这段楼梯一共有多少种方法。
2. 假设一段楼梯共n个台阶，小明一步最多能上3 个台阶，编写程序列出小明上这段楼梯的所有方法

先解决第一个问题：

问题分析：

每一步可能的情况有一个台阶，两个台阶，三个台阶，将台阶总数设为n，方法数设为step(n)，可以得到，迈一个台阶后方法数为step(n-1)，两个台阶后为step(n-2)，三个台阶为step(n-3)，则可得step(n)=step(n-1)+step(n-2)+step(n-3)，发现这是一个往下递归的过程，最终当n=3,2,1时分别可直接数出有4,2,1种方法。

python代码：

    def step(n):if n==1:return 1;if n==2:return 2;if n==3:return 4;sum=step(n-1)+step(n-2)+step(n-3);return sum;

接下来解决第二个问题：

问题分析：

同样按照第一个问题的思路，对于n个台阶，则在原有的步数列表基础上分别产生三个子列表，子列表分别添加步数1,2,3，然后将n-1,n-2,n-3送入下一级函数进行递归，最终进行到n=1或2或3的情况，穷举出其可能的步数添加，即可解决问题。只不过关键在于代码的细节问题，即子列表的生成：分别计算n,n-1,n-2,n-3个台阶方法数（这里第一个问题的函数则可派上用场），同样记为step(x)，将n-1送入下一级函数之前，在原有列表基础上对对应的step(n-1)个列表在后面添加“1”，n-2,n-3同理。

python代码：

    def step(n):if n==1:return 1;if n==2:return 2;if n==3:return 4;sum=step(n-1)+step(n-2)+step(n-3);return sum;def way(n,list,i=0):if n==1:list[i].append(1);return;if n==2:list[i].append(2);list[i+1].extend([1,1]);return;if n==3:list[i].append(3);list[i+1].extend([1,1,1]);list[i+2].extend([1,2]);list[i+3].extend([2,1]);return;for j in range(i,step(n-1)):list[j].append(1);way(n-1,list,i);i=i+step(n-1);for j in range(i,i+step(n-2)):list[j].append(2);way(n-2,list,i);i=i+step(n-2);for j in range(i,i+step(n-3)):list[j].append(3);way(n-3,list,i);def way_achieve(n,list):list=[];for j in range(step(n)):list.append([]);way(n,list);

使用示例：

计算100级台阶：

way_achieve(100,p)   #p为接收列表