递归函数工作原理[亲测有效]

大家好，欢迎来到IT知识分享网。

递归是一种较为特殊的算法，简单来说，“函数”（或者说子程序）不只是能够被其他函数调用（或者引用）的程序单元，在某些语言中函数提供了调用自己的功能，这种功能就是所谓的“递归”。

递归的定义

假如一个函数或者子程序是由自身所定义和调用的，就称为递归。递归至少要定义两种条件：一个是可以反复执行的递归过程，另一个是跳出执行过程的出口。

递归的分类

根据递归调用对象的不同，可以把递归分为以下两种：
1）直接递归：在递归函数中允许直接调用该函数本身
2）间接递归：在递归函数中如果调用其他递归函数，再从其他递归函数调用回原来的递归函数

递归通常用来解决结构自相似的问题。所谓结构自相似，是指构成原问题的子问题与原问题在结构上相似，可以用类似的方法解决。具体地，整个问题的解决，可以分为两部分：第一部分是一些特殊情况，有直接的解法；第二部分与原问题相似，但比原问题的规模小。实际上，递归是把一个不能或不好解决的大问题转化为一个或几个小问题，再把这些小问题进一步分解成更小的问题，直至每个小问题都可以直接解决。因此，递归有两个基本要素：

（1）边界条件：确定递归到何时终止，也称为递归出口。

（2）递归模式：大问题是如何分解为小问题的，也称为递归体。递归函数只有具备了这两个要素，才能在有限次计算后得出结果

在递归函数中，调用函数和被调用函数是同一个函数，需要注意的是递归函数的调用层次，如果把调用递归函数的主函数称为第0层，进入函数后，首次递归调用自身称为第1层调用；从第i层递归调用自身称为第i+1层。反之，退出第i+1层调用应该返回第i层。

递归函数的内部执行过程

一个递归函数的调用过程类似于多个函数的嵌套的调用，只不过调用函数和被调用函数是同一个函数。为了保证递归函数的正确执行，系统需设立一个工作栈。具体地说，递归调用的内部执行过程如下：

（1）运动开始时，首先为递归调用建立一个工作栈，其结构包括值参、局部变量和返回地址；

（2）每次执行递归调用之前，把递归函数的值参和局部变量的当前值以及调用后的返回地址压栈；

（3）每次递归调用结束后，将栈顶元素出栈，使相应的值参和局部变量恢复为调用前的值，然后转向返回地址指定的位置继续执行。 

接下来以一个间接递归为例说明递归的工作原理：

#include<iostream>
using namespace std;
void dif1(int y);
void dif2(int x);

int main()
{
  dif1(21);
  cout<<endl;
  system("Pause");
  return 0;
}

void dif2(int x)
{
  if(x) dif1(x);
}
void dif1(int y)
{
  if(y>0) dif2(y-3);
  cout<<y;
}

这里要注意的是递归调用本质上还是函数调用，既然是函数调用，那么就有一个雷打不动的原则：所有被调用的函数都将创建一个副本，各自为调用者服务，而不受其他函数的影响。
dif函数递归多少次，就会产生多少个副本，再利用内存的栈式管理，反向退出。结合“栈”相关知识，先进后出。

递归，很需要注意的就是死递归，也就是说，某一个函数进入了无限调用自身的情况，永无止境地消耗内存等资源，这在编程方面是一大忌。但凡是递归的函数，一定会在某一个地方存在能够返回上一层函数的代码，否则必定死递归。上述例程中的截至条件为x=0;被调用的函数不会自动结束，因为一旦某个函数A中调用了函数B（或者自己），那么A中的代码会停在调用的位置，而转向B中去执行，同理，如果B又调用函数C，那么B又停在调用的位置，去执行C，如果无限调用，那么程序是永远不会结束的。当然，也有这种情况，A调用B，然后继续自己的代码，不管B的死活，这种是多线程的编程方式，而我们此时讨论的是单线程

最后再来分析下上述例程的执行过程：
求dif1(21)?
一层执行到dif1(21);执行二层dif1(21-3),也就是dif1(18)
三层执行到dif1(15);执行四层dif1(12),第五层dif1(9),第六层dif1(6),第七层dif1(3),此时具体分析下执行过程，dif2(3-3)此时括号中的值为0，不再执行dif1(),而最终的结果遵循栈先进后出的原则，输出结果为：
3 6 9 12 15 18 21
大体过程就是这样的
这里每次一层都相当于一个不同的函数.只要注意一点，调用一次，不是在代码本身上执行，而是会复制出一份再执行，虽然不太恰当，但足以说明问题。