递归的原理

递归是经典算法常用的方法，了解并掌握递归可以大大提升你的程序编写的能力。

1、递归的条件

2、最简单的递归（N的阶层）

3、递归的原理

递归的条件

递归要满足4个条件：分别是 1函数必须有参数、2函数的参数必须改变，3函数必须调用自身，4函数有退出条件。

最简单的递归（N的阶层）

#include <stdio.h>
int factorial(int n){    //1有参数
    if(n==1)             //2有退出条件
        return 1;
    else
        return factorial(n-1)*n;//3调用自身，4参数改变
}

int main() {
    printf("%d",factorial(5));//打印5的阶层
    return 0;
}

执行过程5入栈，4入栈，3入栈，2入栈，依次出栈 1*2*3*4*5。

递归的原理

要理解递归的原理则应该先理解下面这个递归：

#include <stdio.h>
void factorial(int n){    
    if(n==0)           
        return;//退出条件
    else
    {
        printf("A %d\n",n);
        factorial(n-1);//调用自身并且改变参数
        printf("B %d\n",n);
    }
}

int main() {
    factorial(5);
    return 0;
}

运行结果如下：

为什么不是

A 5

B 4

A 3

B 2

...........呢？

这里就出现了递归的机制栈（先入后出），在递归语句之前的先执行，在递归语句之后的放入栈内等递归执行完了再出栈执行。如下图：

蓝的的环最先进入，当要取出它时它是最后一个被取出的。

递归的原理

推荐阅读