详解函数递归

前言

最近被函数递归困恼许久，今天就带领大家一起探秘递归。

什么是递归？

程序调用自身的编程技巧称为递归（ recursion）。

递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接 调用自身的 一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解， 递归策略 只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。

递归的主要思考方式在于：把大事化小。(这个想法很重要)

递归的两个必要条件

1 存在限制条件，当满足这个限制条件的时候，递归便不再继续。

2 每次递归调用之后越来越接近这个限制条件

为了更好的理解递归我将为大家分享几到题目。

题解递归

在解题之前，我想刚刚接触递归的小伙伴都会面临，我知道递归是什么，但就是不会写他或者说不理解怎么实现。为此大家可以参考我的解题三步骤。

步骤一：明确你的函数要实现什么功能。

在我看来，要想求解一个递归你肯定要知道你要实现一个什么功能，写出一大概的函数出来。

//求n的阶乘
int demand_factorial(int n)
{
 
}

在这个代码中，我们明确了这个函数要求的是n的阶乘，求阶乘所需要的参数。

步骤二：寻找递归结束的条件

递归就是在函数在不断的调用自己，要想停下来，肯定是要有条件能让他停下来，不然会一直调用自己而陷入死递归。就是说我们要找到一个参数为啥时，递归结束，之后直接把结果返回。请注意这个参数值我们必须明白，参数为何值的时候，函数的结果是什么。

对于上面那个例子，我们肯定明白n = 1时函数的结果为1。那么我们便可以这么写。

//求n的阶乘
int demand_factorial(int n)
{
  if (n == 1)
  {
    return 1;
  }
}

为什么说当我们明确知道，n = 1时函数结果我们也知道了，n = 1会为递归结束的条件呢。大家可以想我们这个递归是要干什么的，不就是求n的阶乘吗，既然我们都知道到n=1的阶乘为1了，那么到这里就要结束函数递归了。所以说，递归结束的条件：可以理解为我们所知道的函数结果的那个参数值，也就是n是一个很小的值。

步骤三：找出函数的等价条件

就是我们要不断遵循把大事化小的思路，把参数范围不断缩小，我们可以通过一些辅助的变量或者操作，使得原函数的结果不变。

例如，demand_factorial（n）这个范围比较大，我们可以变为demand_factorial（n）=n*

demand_factorial(n-1)，注意n的范围就变成n-1了，为了让原函数不变，我们需要让demand_factorial(n-1)*n.其实，我们就是在为原函数寻找一个等价式。

这一步骤也是最难的大家可以细细体会，下面我们继续完善代码。

//求n的阶乘
int demand_factorial(int n)
{
  if (n == 1)
  {
    return 1;
  }
  else
  {
    return  demand_factorial(n - 1) * n;
  }
}

大家看完上面的思路可能还是不怎么理解，没关系，我会带这个思路继续为大家分享几道题目。

题目1 strlen的模拟（递归实现）

大家继续按照上面的思路来求解这道题目

1 明确你函数要实现的功能。

假设my_strlen（str）是实现求字符串的长度,代码如下：

//用递归模拟strlen
//str为数组名
int my_strlen(char* str)
{
 
}

2 找出递归结束的条件

我们明白在一个字符串中他的结束标志是'\0'，这时函数结果就是0，所以，很明显递归结束的条件为*str='\0'.代码如下

//用递归模拟strlen
//str为数组名
int my_strlen(char* str)
{
  if (*str == '\0')
  {
    return 0;
  }
}

3 找出函数的等价条件

为了求出字符串的长度，我们肯定是从第一个字符开始数，只到数到我们递归结束条件为止。那么该函数的等价为：1+my_strlen(str+1）。其中的my_strlen(str+1)是为了寻找下个字符长度。代码完善如下：

/用递归模拟strlen
//str为数组名
int my_strlen(char* str)
{
  if (*str == '\0')
  {
    return 0;
  }
  else
  {
    return 1 + my_strlen(str + 1);
  }
}

这道题就ok了，大家是否有所体会呢？如果还是不理解我们继续按照这个模式多加练习。

题目2 斐波那契数列

斐波那契数列指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波那契数列以如下被以递推的方法定义： F (0)=0， F (1)=1, F (n)= F (n - 1)+ F (n - 2)，求第n项和。

1 明确你函数要实现的功能。

假设fib(n)是实现求第n个斐波那契数，代码如下:

//求第n个斐波那契数
int fib(int n)
{
 
}

2 找出递归结束的条件

很明显我们知道当n=1或者n=2的时候斐波那契数都为1，所以，递归的结束条件为n<=2,那么函数的返回值便为1.代码如下：

//求第n个斐波那契数
int fib(int n)
{
  if (n <= 2)
  {
    return 1;
  }
}

3 找出函数的等价条件

对于函数的等价条件，题目已经给我们了F (n)= F (n - 1)+ F (n - 2)，所以，代码完善如下：

//求第n个斐波那契数
int fib(int n)
{
  if (n <= 2)
  {
    return 1;
  }
  else
  {
    return fib(n - 1) + fib(n + 2);
  }
}

题目3 小青蛙跳台阶问题

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

1 明确你函数要实现的功能

假设 (n) 的功能是求青蛙跳上一个n级的台阶总共有多少种跳法，代码如下：

//小青蛙跳台阶问题
int jump(int n)
{
 
}

2 找出递归结束的条件

上面说了，求递归结束的条件，你直接把 n 范围变的很小就好，因为 n 越小，我们就越容易直观着算出 f(n) 的多少，所以当 n = 1时，我们很容易知道 f(1) = 1。代码如下：

//小青蛙跳台阶问题
int jump(int n)
{
  if (n == 1)
  {
    return 1;
  }
}

3 找出函数的等价条件

我们知道青蛙每次跳台阶，可以跳一个台阶，也可以跳二个台阶，所以说青蛙每次跳台阶都有二种跳法。

第一种跳法，第一次跳1个台阶，那么还有n-1个台阶没跳，剩下的n-1个台阶有jump(n-1)种跳法。

第二种跳法，第一次跳2个台阶，那么还有n-2个台阶没跳，剩下的n-2个台阶有jump(n-2)种跳法。

所以青蛙所以跳法为：jump(n-1)+jump(n-2)，即等价关系式为：jump(n)=jump(n-1)+jump(n-2)代码如下

//小青蛙跳台阶问题
int jump(int n)
{
  if (n == 1)
  {
    return 1;
  }
  else
  {
    return jump(n - 1) + jump(n - 2);
  }
}

大家认为上面的代码对吗?嘻嘻既然我这么问了，肯定是有问题的了，当我们把代码运行起来的时候会发现，代码死递归了，这个时候问题肯定就出现在递归条件上了，我们的递归条件是不严谨的。当n=2时，显然，jump(2)=jump(1)+jump(0),我们知道jump(0)=0，按道理递归该结束，但是我们上面代码的逻辑中会继续调用jump(0)=jump(-1)+jump(-2),这样就会导致进入死循环，无限调用。

为了防止出现递归结束条件出现不严谨的现象，我们每次进行第三步后，应该返回第二步，看根据函数的调用关系会不会出现一些漏掉的一些结束条件。当我们把条件补全，代码如下：

//小青蛙跳台阶问题
int jump(int n)
{
  if (n <= 2)
  {
    return n;
  }
  else
  {
    return jump(n - 1) + jump(n - 2);
  }
}

今天题目就和大家做到这里了，大家如果还觉的不过瘾。我在后面为大家准备了几道题目大家可以去练习。下面我要继续为大家分享有关递归于迭代的问题。

递归与迭代

我想对大家说是并不是所有复杂问题，都可以用递归来解决，就算可以也会出现许多问题。我们继续回到斐波那契数列问题。

//求第n个斐波那契数
int fib(int n)
{
  if (n <= 2)
  {
    return 1;
  }
  else
  {
    return fib(n - 1) + fib(n - 2);
  }
}

当我们求的第n的比较大的时候，代码会报错，stack overflow（栈溢出） 这样的信息。

系统分配给程序的栈空间是有限的，但是如果出现了死循环，或者（死递归），这样有可能导致一 直开辟栈空间，最终产生栈空间耗尽的情况，这样的现象我们称为栈溢出。

为什么说当n很大的时候会，会出现报错呢？当n=50时，我们来看下面这幅图。

我们为了求f(50)就要知道f(49)于f(48)以此类推，将会导致出现许多不必要的调用。

当我们修改一下代码

int count = 0;//全局变量
int fib(int n)
{
 if(n == 3)
 count++;
 if (n <= 2)         
 return 1;
 else
 return fib(n - 1) + fib(n - 2);
}

会发现count是个很大的值，也就是说f(3)被重复调用了许多次。这样我们就不难找出当n是个很大的值的时候为什么会报错了，很明显这里将会栈溢出。

这里我们用迭代的方法写一下将会解决栈溢出的问题。

//求第n个斐波那契数
int fib(int n)
{
  int result;
  int pre_result;
  int next_older_result;
  result = pre_result = 1;
  while (n > 2)
  {
    n -= 1;
    next_older_result = pre_result;
    pre_result = result;
    result = pre_result + next_older_result;
  }
  return result;
}

总结：

1我们在用递归的时候是为了更好的解决问题，因为他形式更加清晰

2当发现递归会出现栈溢出的现象时不妨换用迭代的方式解决。

练习题

题目1 打印一个数的每一位

类容：

递归方式实现打印一个整数的每一位

题目2 字符串逆序（递归实现）

类容：

编写一个函数 reverse_string(char * string)（递归实现）

实现：将参数字符串中的字符反向排列，不是逆序打印。

要求：不能使用C函数库中的字符串操作函数。

比如:

char arr[] = "abcdef";

逆序之后数组的内容变成：fedcba

题目3 递归实现n的k次方

内容：

编写一个函数实现n的k次方，使用递归实现。

题目4 汉诺塔问题

内容：

相传在古印度圣庙中，有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上，有三根杆(编号A、B、C)，在A杆自下而上、由大到小按顺序放置64个金盘(如图1)。游戏的目标：把A杆上的金盘全部移到C杆上，并仍保持原有顺序叠好。操作规则：每次只能移动一个盘子，并且在移动过程中三根杆上都始终保持大盘在下，小盘在上，操作过程中盘子可以置于A、B、C任一杆上。请用递归实现。

结束语

今天就分享到这里吧，递归还是挺难的，大家还是要做几到题目，不理解的地方还可以画图理解。希望我的分享能对大家有点帮助，喜欢的话来个三连吧！