剑指offer笔记（十）递归和循环

末蓝、 2022-10-10 12:49 93阅读 0赞

# 递归和循环 #

### 什么是递归？ ###

递归就是在一个函数内部调用函数本身

### 什么是循环？ ###

循环通过设置计算初始值及终止条件，在此范围内重复计算

举例说明一下：

1+2+3+...+n求和

//循环
    int sum(int n)
    {
        int res=0;
        for(int i=1;i<=n;i++)
        {
            res+=i;
        }
        return res;
    }
    
    //递归
    int sum(int n)
    {
        return n==0?0:n+sum(n-1);
    }

从上述代码可以明显感觉到：递归简洁明了

但递归也存在一定的不安全性：

（1）我们都知道函数调用需要在内存栈中分配空间以保存参数，返回地址及临时变量，以及数据压栈和出栈都需要时间，而递归每一次调用函数本身都需要时间和空间开销

（2）递归本质是分治思想，化大为小，但如果小问题如果存在相互重叠部分，导致很多计算都是重复

（3）每一次函数调用在内存中分配空间，而每个进程的栈容量都是有限，调用层数过多就会导致栈溢出

一说起递归，或许大家都可以想到最为经典的斐波那契数列

//递归
    int fibonacci(int n)
    {
        if(n<=0)
            return 0;
        if(n==1)
            return 1;
        return fibonacci(n-1)+fibonacci(n-2);
    }
    
    //迭代
    int fibonacci(int n)
    {
        if(n<2)
            return n;
        int f1=0;
        int f2=1;
        int fn;
        for(int i=2;i<=n;i++)
        {
            fn=f1+f2;
            f1=f2;
            f2=fn;
        }
        return fn;
    }

上述代码中，第一种为递归实现，第二种为利用递归思想通过循环迭代实现，递归实现虽然简单，但是如果n过大就会导致时间复杂度过高，甚至导致栈溢出，其主要原因就是存在过多重复计算，采用第二种方法有效保存已经计算过的结果，大大降低时间复杂度