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

饭-米粒

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

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

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

#网上找的
def tree(traget):
    if traget == 0:
        return 1
    if traget == 1:
        return 1
    return tree(traget-1)+tree(traget-2)

#print(tree(5))

#自己写的
a=[]
def tree2(traget,a):
    if traget <0:               #多操作，此数据无效
        return False
    elif traget == 0:           #正好上完，打印上楼序列
        print(a)
    else:
        for i in [1,2]:         #用上1级和2级循环试验
            s=a[:]
            s.append(i)         #将上的楼梯数填入列表
            tree2(traget-i,s)   #剩余的楼梯，继续爬
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，没关注到重点，这里是想输出上楼的序列，用递归的话，试下这样

def tree(result,way,target):
        if target == 0:
                result.append([*way])
                return result
        if target == 1:
                way.append(1)
                result.append([*way])
                return result
        tree(result,[*way,1],target-1)
        tree(result,[*way,2],target-2)
        return result
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)就是它的递归调用写成代码就是：

def f(x):
  if x<=0:
    return x
  else:
    return x+f(x-1)
    

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

isdkz

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

好的，明白了，谢谢大佬

2012277033

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

def tree(result,way,target):
        if target == 0:
                result.append([*way])
                return result
        if target == 1:
                way.append(1)
                result.append([*way])
                return result
        tree(result,[*way,1],target-1)
        tree(result,[*way,2],target-2)
        return result
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进行操作。
打个比方

a=[1,2,3]
b=[*a]
idcheck = id(a) == id(b)
check = a==b
print(a)
print(b)
print(idcheck)
print(check)
# 输出的结果是
# [1,2,3]
# [1,2,3]
# False
# True

如果用一般的赋值

a=[1,2,3]
b=a
idcheck = id(a) == id(b)
check = a==b
print(a)
print(b)
print(idcheck)
print(check)
# 输出的结果是
# [1,2,3]
# [1,2,3]
# True
# True