一、什么是递归函数

所谓递归函数,就函数自己调用自己,至于为什么自己调用自己就被称为递归呢?
这个问题我们后面再回答

递归函数举例:

#include <stdio.h>

long sum(int n) 
{
    if(1==n) 
    {
        return 1;
    }
    else 
    {
        return ( n + sum(n-1) );//sum函数自己调用自己,所以sum函数就是一个递归函数。
    }
}

int main(void) 
{
    int a = 0;

    a = sum(3);

    printf("a = %d\n", a);

    return 0;
}

疑问:这个递归函数的作用是什么?

答:对0~3的做累加运算,既然能计算03之间的累加和,自然也能计算0~n的累加,
比如做100的累加时,只要把代码中sum(3)改为sum(100),即可计算0~100的累加

当然累加计算时,也可以通过循环来实现,我们这里之所以使用递归来实现,主要是想通过这个例子来介绍递归。

int i = 0;
for(i=0; i<=100; i++)
{
    sum = sum + i;
}

二、分析这个递归函数

  • 1)递归次数:2次,也就是说,sum函数自己调用自己的次数只有两次,main函数调用sum的那一次不算
  • 2)递与归:“递”是一级一级调用的过程,“归”是一级一级返回的过程
  • 3)当n=1时,整个递归就开始一级一级返回,所以n==1就是递归返回条件
  • 4)递归在一级一级调用时,只是在做计算的准备,只有当一级一级返回时,才开始在真正的计算,
    回到最开始调用sum的位置时,整个计算结果就出来了

总结递归算法特点

  • 1)递归就是函数自己调用自己
  • 2)递归次数就是自己调用自己的次数
  • 3)递归中的“递”就是一级一级调用的过程,“归”就是一级一级返回的过程
  • 4)递归必须要有终止条件,不能没完没了的调用下去

三、 直接递归和间接递归

(1)直接递归:函数自己直接调用自己,上面的例子就是直接递归。
(2)间接递归:间接递归就是自己先调别的函数,别的函数再调自己


四、如何分析别人给的递归函数

阅读源码时或者面试时,可能需要分析别人的递归函数,
那么我们应该如何分析别人的递归函数,搞清递归的目的呢

分析方法很简单,以我们自己的递归例子为例,我们只要降低递归次数,
将次数少的递归过程分析明白了,自然就能清楚这个递归是干嘛的

不过分析递归时,千万不要只拿眼睛看,一定要像我之前一样,耐心画出递归的过程图,
只要能够把递归过程图画出来,很容易就能搞清楚这个递归作用,
当然了,不用画的像我那么精细,画个草图就行

对于直接递归来说,分析起来较为容易,但是间接递归的分析稍微难一些,不过分析方法也是一样的,
一般只要将5~7次的递归过程分析清楚了,基本就能搞清楚递归的作用


五、递归的优点和缺点

优点

使用递归解决问题时,程序代码会比较干脆、简洁。

缺点:不容易被人理解和阅读,而且非常消耗栈内存空间

栈内存消耗的很严重时,递归甚至可能会导致“栈边界”溢出
所谓溢出就是,由于递归的某些问题,在递归调用时导致了栈的过分消耗,严重时甚至越过了栈边界跑到堆空间,
将堆空间内容给修改了,最后直接会导致整个程序的崩溃

有些黑客有时就会利用递归的“栈边界溢出”特性来进行攻击,从而瘫痪被攻击的程序

递归的”返回判断条件”其实也被称为“边界保护条件”,为什么称为边界保护条件呢?

因为它防止递归无限制运行下去,从而防止栈边界溢出,所以才被称为“边界保护条件”

导致栈溢出的情况有哪些呢?

  • 1)忘了给“递归返回条件”,使得递归无限进行下去
  • 2)递归算法有问题,使得递归次数太多,导致递归调用太深,深到大量消耗栈内存
#include <stdio.h>

int fun(int n)
{
    int ret = 0;

    if(n == 1) 
    {
        return 1;
    }
    else
    {
        ret = n + fun(n-1);
        ret = ret + n + fun(n-1);
    }

    return  ret;
}

int main(void)
{
    int ret = 0;

    ret = fun(50);

    printf("%d\n", ret);

    return 0;
}

为什么上面这个递归有问题?

由于递归时有两次调动函数,你去跟踪这个递归时,你会发现随着fun(n)中数字的增加,递归次数会急剧增加,
n达到30时,这个递归很久都不会结束,如果将n改为100的话,情况会更严重,几乎等不到结束

所以从这个例子可以看出,对于递归来说仅有返回条件还是不够的,如果递归算法本身有问题的话,同样不行,
对于这个例子来说,要么优化这个递归,要么干脆不要使用递归,换一种非递归的方式来代替实现


六、我们应该如何看待递归的使用

递归算法的缺点是明显的,因此但凡能不用递归时就不使用递归,正是基于这一原则,
不少公司为了让自己的软件能够更加的稳定,往往会对“递归”的使用加以限制,
只有当非递归不可时才使用,但凡有更好算法时就不会使用递归

比如之前的递归求和,其实就可以不使用递归,我们可以使用两种方法来替代递归,
所以真实的累加求和运算,我们是不会使用递归来做的

1)替代方法1:使用while循环代替
使用while循环来实现,这个在前面已经介绍过,对于大部分的递归来说,
其实都可以使用while循环来代替,如果使用循环来代替,循环比递归更好

当然,如果有比循环更好的方法,自然是最好的,比如累加求和,其实就有比循环更好的方法,
那就是“方法2:高斯算法”

2)替代方法2:高斯算法
高斯算法的公式:sum = n/2 * (1 + n)

那么0~100的求和:sum = 100/2 * (1 + 100)
最终:sum = 5050

从这个例子可以看出,为什么对于哪些真正做算法的人来说,对数学有很高的要求了,因为如果你数学够牛,
你就能通过数学算法来优化程序的算法,提高程序的效率

当然,大家千万不要因为听我说数学很重要,你就去研究数学,然后想去做算法,
事实上对于我们应用工程来说,算法不是重点,我们的重点是开发产品,
如果真要用到什么算法,我们只要能够调用别人的算法库即可