|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
1、递归是一种解决问题的方法,将问题分解成规模更小的问题,不断地调用自身,解决小问题,直至问题不可再分。
递归一般都是从结束条件一步一步往回计算
【我的疑问】:递归一般都是从结束条件一步一步往回计算----这句话没看懂
以下面例子为例:
# p6_8.py
def fib(n):
if n < 1:
print('输入有误!')
return -1
if n == 1 or n == 2:
return 1
else:
return fib(n - 1) + fib(n - 2)
结束条件指的是fib(1) = fib(2) = 1,哪从这个结束条件一步一步往回计算其中的往回计算是什么意思?指数列往左还是数列往右?指树结构往上还是树结构往下?
2、自定义函数fib求第n个斐波那契值:采用包括0在内的完整数列即0 1 1 2 3 ……
# p6_test_.py
def fib(n):
if n == 0: # 当n为0时返回0
return 0
elif n == 1: # 当n为1时返回1,实际n == 2时也是return 1,所以也可写成elif n == 1 or n == 2: 或 elif n in [1, 2]:
return 1
else: # 此行可以不要,但下行缩进需要提前!
return fib(n - 1) + fib(n - 2) # 当n大于1时,用递归的方法调用函数求第n-1和第n-2个斐波那契值
n = int(input('please input:'))
print(fib(n))
语句 return fib(n-1)+fib(n-2)的意思就是向前求斐波那契值,直到n-1=1,n-2=0,因为只有第1个和第0个斐波那契值是确定的
【我的疑问】
---语句 return fib(n-1)+fib(n-2)的意思就是向前求斐波那契值,其中的向前又是什么意思?
---直到n-1=1,n-2=0,因为只有第1个和第0个斐波那契值是确定的。这句话也没看懂,n-1=1,n-2=0,和第1个和第0个斐波那契值是确定的之间有什么关系?
递归是一种将问题拆分成更小的子问题来解决的方法。
在斐波那契数列例子中,使用递归的方法计算第n个斐波那契数列的值,可以看做不断把问题“向前推进”:
- 当 n=1 或 n=2 时,斐波那契数列的值已知,直接返回 1;
- 当 n>2 时,我们需要计算第 n-1 和第 n-2 个斐波那契数列的值,这两个问题是比原问题更简单的问题,于是我们可以用同样的方法递归解决它们;
- 对于计算第 n-1 个斐波那契数列的值,我们需要先计算第 n-2 和第 n-3 个斐波那契数列的值;
- 对于计算第 n-2 个斐波那契数列的值,我们需要先计算第 n-3 和第 n-4 个斐波那契数列的值;
- ……
- 直到计算到第 1 或 2 个斐波那契数列的值时,递归开始回溯;
- 逐层返回每个子问题的解,最终得到第 n 个斐波那契数列的值。
在递归过程中,每一次递归调用都会把问题规模缩小,直到问题规模变得足够小,可以直接计算出来而不用递归了,这就是递归的结束条件。当递归到最后一层时,我们需要不断回溯并把每一层的结果汇总起来得到最终的答案。
|
|