剑指offer读书笔记-递归与循环

剑指offer读书笔记-递归与循环

一、递归与循环概述

 递归是在一个函数的内部调用这个函数自身。但是循环时通过设置计算的初始值以及终止条件,比如求:1+2+3+…+n,我们可以使用递归或者循环两种方式求出结果。

int AddFrom1ToN_Recursive(int n)
{
    return n <= 0 ? 0:n + AddFrom1ToN_Recursive(n-1);
}

int AddFrom1ToN_Iterative(int n)
{
    int resultc = 0;
    for(int i = 1; i <= n; ++i)
    {
        result += i;
    }

    return result;
}

递归的缺点:递归由于是函数调用自身,而函数调用是有时间和空间的消耗的:每一次函数调用,都需要在内存栈中分配空间以保存参数、返回地址以及临时变量,而且往栈中压入数据和弹出数据都需要时间。同时递归中很多计算都是重复的,递归地本质是将一个问题划分成两个或者多个小问题。如果多个小问题存在相互重叠的部分,就存在重复的计算。递归还有一个严重的问题就是:栈溢出,每一个进程的栈的容量是有限的,当递归调用的层级太多时,就会超出栈的容量。

二、效率低下的解法

long long Fibonacci(unsigned int n)
{
    if(n < 0)
    {
        return 0;
    }
    if(n < 1)
    {
        return 1;
    }
    return Fibonacci(n - 1) + Fiboncci(n - 2);
}

当递归100次时,效率非常差。

三、面试官期待的解法

 上述递归代码之所以慢,是因为重复的计算太多,我们只要避免重复计算就可以了。

从下往上计算,首先根据f(0)和f(1)计算f(2),再根据f(1)和f(2)计算(3)以此类推,计算f(n)

long long Fibonacci(unsigned n)
{
    int result[2] = {0,1};
    if(n < 2)
    {
        return result[n];
    }

    long long fibNMinusOne = 0;
    long long fibNMinusTwo = 1;
    long long fibSum = 0;

    for(unsigned int i = 2; i <= n)
    {
        fibSum = fibNMinusOne + fibNMinusTwo;
        fibNMinusOne = fibNMinusTwo;
        fibNMinusTwo = fibSum;
    }
    return fibSum;
}

你可能感兴趣的