该系列文章为本人刷leetcode的记录,主要旨在分享刷题的思路及算法解析(尽可能的一题多解),另方便自己日后查阅回顾。代码的实现语言是python和go。
想进大厂厂免不了刷题,一起加油吧，小伙伴们！
题目 offer 第10题 菲波那切数列链接: https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof/
题目内容写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：
F(0) = 0, F(1) = 1 F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
示例 1：
输入：n = 2 输出：1
示例 2：
输入：n = 5 输出：5
提示：
- 0 <= n <= 100
分析:
该题具有明显的递归公式;因此肯定可以考虑用递归来解;同时有递归的解法的话,非递归的迭代解法一般也能解此题;
但注意对于有明显的递归公式f(n)=f(n-1)+f(n-2)的递归程序来说;递归是一直递归到最底,之后开始依次向上返回;每一次返回的值都与上一次递归的结果相关;
因此在递归调用的过程当中计算机为每一层的返回点、局部量等开辟了栈来存储，递归次数过多容易造成栈溢出。
所以一般面对复杂的递归过程,有时候可以考虑用尾递归来解决;
尾递归:
就是从最后开始计算, 每递归一次就算出相应的结果, 也就是说, 函数调用出现在调用者函数的尾部, 因为是尾部, 所以根本没有必要去保存任何局部变量. 直接让被调用的函数返回时越过调用者, 返回到调用者的调用者去。尾递归就是把当前的运算结果（或路径）放在参数里传给下层函数，深层函数所面对的不是越来越简单的问题，而是越来越复杂的问题，因为参数里带有前面若干步的运算路径.
简单来说:递归的调用函数f(n, sum) = f(n-1) + value(n) ; 会保存n个函数调用堆栈，而使用尾递归f(n, sum) = f(n-1,value(n))； 这样则只保留后一个函数堆栈即可，之前的可优化删去。(其实递归就是向下递归,向上返回;而尾递归就是向下递归的同时也带上了上一个递归的返回值,只需要在最后一个递归中进行返回即可.所以只需要开辟一个栈)
代码实现 pythondef fib(n:int) ->int:
#方法1:尾递归;这题用递归会超时;
# def fibtail(n,f1,f2):
# if n==0:return 0
# elif n==1: return 1
# elif n==2: return f2+f1
# #尾递归最大的特点就是在向下递归的时候也在计算,将上一层计算的结果带给下一层的递归;
# #这里就很明确;在n>2时,求f(n)的过程也是从f(2)、f(3)、f(4)、f(5)、、、一直求到f(n);
# #所以n在n--到n=2的过程中,将就是直接可以看成在一直求f(2)...到f(n). 因为倒序计算的次数和正序计算的次数完全一样;
#
#
# else: return fibtail(n-1,f2,f1+f2)
#
#
# return fibtail(n,0,1)
#方法2:非递归的迭代解法
if n<2: return n
else:
f0,f1= 0,1
for i in range(2,n+1):
fn = f0+f1
f0 = f1
f1 = fn
return fn
go
func fib(n int) int{
//方法1:尾递归
const mod int = 1e9 + 7
var fib_tail func(n,f0,f1 int) int
fib_tail = func(n,f0,f1 int) int{
if n==0{return 0
}else if n==1{return 1
}else if n==2{return (f0+f1)%mod
}else {
return fib_tail(n-1,f1%mod,(f0+f1)%mod) //这里两个参数都需要取余
}
}
return fib_tail(n,0,1)
// //方法2:迭代
// fn := 0
// if n<2{return n
// }else{
// f0,f1 := 0,1
// for i:=2; i
总结
未经论证的个人总结:对于尾递归来说，其能解决的问题是只需要返回最后一步结果的问题,比如解决阶乘问题;解决菲波那切数列数列问题;
def factorial_tail(n,ret):
if n<0:return 0
elif n==0:return 1
elif n==1: return 1*ret
else: return factorial_tail(n-1,n*ret)
def fib_tail(n,f0,f1):
if n==0: return 0
elif n==1: return 1
elif n==2: return f0+f1
else: return fib_tail(n-1,f1,f0+f1)
以上都可以看出对阶乘来说从1、2、3…到n的阶乘与从n、n-1、n-2…到1的阶乘完全一样;尾递归就是在倒过来计算;
"""
如下对阶乘来说就是首先确定尾递归向下递归到哪一层;
比如阶乘是计算到n=1后就停止并进行返回,那么写好该层应该返回的参数1*(ret)
而factorial_tail(n-1,n*ret)就是倒序来计算 n*(n-1)*(n-2)...(2) 后面的(n-1)*(n-2)...2用ret代替； 其中函数的第一个参数n-1就是表示还要计算多少次;(因为该层已经计算了一次)
"""
n==1: return 1*ret
return factorial_tail(n-1,n*ret)
"""
同理,对于菲波那切数列一样,直接将其看成从n=2一直加到n=n即可; fib_tail(n-1,f1,f0+f1)表示进行第一次计算;
"""
n==2: return f0+f1
return fib_tail(n-1,f1,f0+f1)
还有需要注意下取余的操作;防止数据溢出
