[剑指-07](php&python):斐波那契数列

说明：记录刷剑指offer，使用php与python两种语言，对解题思路以及涉及到的基本语法以及知识点做学习记录。其中对于每道题目进行粗略的分类。

题目来源

• 分类：递归
• 斐波那契数列

题目描述

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。
n<=39

解题思路

斐波那契数列为：1,1,2,3,5,8,13....
公式为：

观察数列的特性，使用递归解决问题此题没有办法通过，时间超过限制），当使用递归方法实现时，时间复杂度和空间复杂度都太大。由于函数调用自身，而函数调用是有时间和空间消耗的：每一次函数调用，都需要在内存栈中分配空间以保存参数，返回地址及临时变量，而且往栈里压入数据和弹出数据都需要时间。因此，此题使用迭代的方法解决。

编程实现

PHP

<?php
// 递归（不通过）
function Fibo($n){
        if ($n == 0) {
            return 0;
        }
        if ($n == 1) {
            return 1;
        }
        
        return Fibo($n - 1) + Fibo($n - 2);
    }
// 迭代
function Fibonacci($n)
{
    // write code here
    $f1 = 0;
    $f2 = 1;
    if($n == 0){
        return 0;
    }
    if ($n == 1){
        return 1;
    }
    for($i = 2; $i <= $n; $i++){
        $temp = $f1 + $f2;
        $f1 = $f2;
        $f2 = $temp;
    }
    return $temp;
}

Python

运行时间：26ms

占用内存：5728k
# -*- coding:utf-8 -*-
class Solution:
    def Fibonacci(self, n):
        a, b = 0, 1
        for i in range(n):
            # print i
            a, b = b, a+b
        return a