算法学习<3>---递归

引言

数据结构和算法对于程序员来说相当重要，我最近打算学习这一门课程，并以博客的形式记录自己的学习过程和心得，目前暂时从两本书入手，一本是《大话数据结构》，一本书《算法图解》，我先从《算法图解》，这本手开始学习吧。如果你最近也在学习，关注一波，一起学习，一起进步吧~

递归

递归的定义

我们把一个直接调用自己或者通过一系列的调用语句调用自己的函数称为递归函数,每个递归函数都有两部分：基线条件（base case）和递归条件（recursive case）。递归条件指的是函数调用自己，而基线条件则指的是函数不再调用自己，从而避免形成无限循环。

每个递归定义必须有一个条件，使得递归不再进行而是返回退出

来看一个经典的例子—斐波那契数列

如果兔子在出生两个月后就有繁殖能力,一对兔子每个月能生出一对小兔子出来。假设所有的兔子都不死，那么一年后可以繁殖多少对兔子？

这个数列有一个明显的特征：

前两项相邻之和等于后一项的值; 在数学上我们可以这么表示:

用C语言递归实现上述问题

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//菲波那契递归函数
int fibonacci(int i)
{
	if(i < 2)//基线条件
		return i == 0 ? 0 : 1;
	return fibonacci(i-1)+fibonacci(i-2);
}

int main(int argc, char* argv[])
{
	
	if(argc != 2)
		printf("parameter error! Please re-enter");
	
	printf("The rabbit have %d",fibonacci(atoi(argv[1])));
	printf("\n");
}

执行结果

上面的程序，感兴趣的话你可以试试参数修改为100000。你的程序应该会崩溃掉~

栈

为什么程序会崩溃呢？你可能还没意识到,我们刚刚的递归,其实是用到了栈。如果不停的递归压入栈中，栈会“爆掉”。

使用栈虽然很方便，但是也要付出代价：存储详尽的信息可能占用大量的内存。每个函数调用都要占用一定的内存，如果栈很高，就意味着计算机存储了大量函数调用的信息。在这种情况下，你有两种选择。 重新编写代码，转而使用循环。 使用尾递归。这是一个高级递归主题，这里暂且不讨论。另外，并非所有的语言都支持尾递归。

小结

递归指的是调用自己的函数。 每个递归函数都有两个条件：基线条件和递归条件。 栈有两种操作：压入和弹出。 所有函数调用都进入调用栈。 调用栈可能很长，这将占用大量的内存。