python上台阶问题 递归
时间: 2023-09-23 21:04:45 浏览: 79
这是一个递归问题,我们可以使用递归函数来解决。
假设我们要上n个台阶,我们可以把问题分解为如下两个子问题:
1. 当我们迈出第一步时,我们还剩下n-1个台阶要走;
2. 当我们迈出第一步时,我们还剩下n-2个台阶要走;
因此,我们可以得到如下递归式:`f(n) = f(n-1) + f(n-2)`。
其中,`f(n)` 表示走完n个台阶的方式数。
当 n = 1 时,只有一种走法;当 n = 2 时,有两种走法,分别是一步一步和一次性跨两步。
下面是Python代码实现:
```python
def climbStairs(n: int) -> int:
if n == 1:
return 1
if n == 2:
return 2
return climbStairs(n-1) + climbStairs(n-2)
```
测试一下:
```python
print(climbStairs(3)) # 输出3,即有3种方式可以走完3个台阶
print(climbStairs(4)) # 输出5,即有5种方式可以走完4个台阶
```
需要注意的是,递归函数虽然直观易懂,但是当n较大时,递归深度会越来越大,导致程序的效率变得很低。因此,可以考虑使用循环或者动态规划来优化算法。
相关问题
python青蛙跳台阶递归
青蛙跳台阶是一个经典的递归问题,也是Python学习中的一个重要练习。题目是这样的:一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。这个问题可以使用递归来解决,递归函数的代码如下:
```
def jumpFloor(n):
if n == 1:
return 1
elif n == 2:
return 2
else:
return jumpFloor(n-1) + jumpFloor(n-2)
```
这个递归函数的思路是:当n等于1时,只有一种跳法;当n等于2时,有两种跳法;当n大于2时,可以先跳一级台阶,剩下的n-1级台阶就有jumpFloor(n-1)种跳法;或者先跳两级台阶,剩下的n-2级台阶就有jumpFloor(n-2)种跳法。因此,总的跳法数就是这两种情况的和。
使用python青蛙跳台阶递归
青蛙跳台阶问题是一个经典的递归问题,可以使用Python编写递归函数来解决。下面是一个使用Python实现青蛙跳台阶递归的示例代码:
```
def frog(n):
if n == 1:
return 1
if n == 2:
return 2
return frog(n-1) + frog(n-2)
sum = frog(10)
print("sum = ", sum)
```
在这个示例代码中,我们定义了一个名为`frog`的递归函数,它接受一个参数`n`,表示台阶的数量。如果`n`等于1或2,那么直接返回1或2。否则,递归调用`frog`函数来计算跳上`n-1`和`n-2`级台阶的跳法总数,然后将它们相加并返回结果。
在主程序中,我们调用`frog`函数来计算跳上10级台阶的跳法总数,并将结果打印到控制台上。