[已解决]我这写的算递归么？问题：求上楼梯的方法数，可选择1级或2级，有什么好办法输出序列吗

饭-米粒

有什么其他办法输出每个方法的序列么，想了好久，不知道用什么办法
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?

注意：给定 n 是一个正整数。

输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
注意：最好输出上楼的步骤

1. #网上找的
   
2. def tree(traget):
   
3.     if traget == 0:
   
4.         return 1
   
5.     if traget == 1:
   
6.         return 1
   
7.     return tree(traget-1)+tree(traget-2)
   
8. 
   
9. #print(tree(5))
   
10. 
    
11. #自己写的
    
12. a=[]
    
13. def tree2(traget,a):
    
14.     if traget <0:               #多操作，此数据无效
    
15.         return False
    
16.     elif traget == 0:           #正好上完，打印上楼序列
    
17.         print(a)
    
18.     else:
    
19.         for i in [1,2]:         #用上1级和2级循环试验
    
20.             s=a[:]
    
21.             s.append(i)         #将上的楼梯数填入列表
    
22.             tree2(traget-i,s)   #剩余的楼梯，继续爬
    
23. tree2(5,a)

复制代码

运行结果：
[1, 1, 1, 1, 1]
[1, 1, 1, 2]
[1, 1, 2, 1]
[1, 2, 1, 1]
[1, 2, 2]
[2, 1, 1, 1]
[2, 1, 2]
[2, 2, 1]

我这写的算递归吗？像穷举的意思
大佬们有什么好办法输出上楼梯的序列吗？

最佳答案

月排行榜 / 总排行榜

2012277033

2022-2-19 11:12:13

sorry，没关注到重点，这里是想输出上楼的序列，用递归的话，试下这样

1. def tree(result,way,target):
   
2.         if target == 0:
   
3.                 result.append([*way])
   
4.                 return result
   
5.         if target == 1:
   
6.                 way.append(1)
   
7.                 result.append([*way])
   
8.                 return result
   
9.         tree(result,[*way,1],target-1)
   
10.         tree(result,[*way,2],target-2)
    
11.         return result
    
12. print(tree([],[],5))

复制代码

跳转到最佳答案楼层

wp231957

在函数内部调用自己，这是递归，比如前7行
至于你写的自然不算

qq1151985918

网上找的是递归，你写的那个不是

isdkz

qq1151985918 发表于 2022-2-18 09:04
网上找的是递归，你写的那个不是

他写的那个不是有调用自己了吗？

2012277033

isdkz 发表于 2022-2-18 13:40
他写的那个不是有调用自己了吗？

递归，有入参，有返回，他这个只有traget<0的时候返回false，但是没有接收。在其他情况下都没返回。比如递归条件：f(x)的返回值，当x<=0的时候返回x，其他情况下返回x+f(x-1).这里x<0就是它的出口，f(x-1)就是它的递归调用写成代码就是：

1. def f(x):
   
2.   if x<=0:
   
3.     return x
   
4.   else:
   
5.     return x+f(x-1)
   
6.    

复制代码

这是一个累加的方法。这是一个递归调用。它自己写的那部分，更像是迭代。。

isdkz

2012277033 发表于 2022-2-18 14:44
递归，有入参，有返回，他这个只有traget

好的，明白了，谢谢大佬

2012277033

sorry，没关注到重点，这里是想输出上楼的序列，用递归的话，试下这样

1. def tree(result,way,target):
   
2.         if target == 0:
   
3.                 result.append([*way])
   
4.                 return result
   
5.         if target == 1:
   
6.                 way.append(1)
   
7.                 result.append([*way])
   
8.                 return result
   
9.         tree(result,[*way,1],target-1)
   
10.         tree(result,[*way,2],target-2)
    
11.         return result
    
12. print(tree([],[],5))

复制代码

饭-米粒

2012277033 发表于 2022-2-19 11:12
sorry，没关注到重点，这里是想输出上楼的序列，用递归的话，试下这样

大佬，可以告诉下*way，*的作用名称吗？
百度不出来
感觉这玩意比较神奇
print(*way) = 1 1 1 1 1
ways = [*way]
print(ways) = [1,1,1,1,1]
w=[1 2 3]就报错

2012277033

饭-米粒 发表于 2022-2-19 13:33
大佬，可以告诉下*way，*的作用名称吗？
百度不出来
感觉这玩意比较神奇

就是解包，将里面所有的元素提取出来。这样是避免出现多个地方使用了同一个way进行操作。
打个比方

1. a=[1,2,3]
   
2. b=[*a]
   
3. idcheck = id(a) == id(b)
   
4. check = a==b
   
5. print(a)
   
6. print(b)
   
7. print(idcheck)
   
8. print(check)
   
9. # 输出的结果是
   
10. # [1,2,3]
    
11. # [1,2,3]
    
12. # False
    
13. # True

复制代码

如果用一般的赋值

1. a=[1,2,3]
   
2. b=a
   
3. idcheck = id(a) == id(b)
   
4. check = a==b
   
5. print(a)
   
6. print(b)
   
7. print(idcheck)
   
8. print(check)
   
9. # 输出的结果是
   
10. # [1,2,3]
    
11. # [1,2,3]
    
12. # True
    
13. # True

复制代码