问题介绍：
- 假设一段楼梯共n个台阶，小明一步最多能上3 个台阶，编写递归函数计算小明上这段楼梯一共有多少种方法。
- 假设一段楼梯共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为接收列表
