递归问题的初级理解

数学归纳法

数学归纳法是数学中常见的证明方法，高中数学中的数列证明中就有提到。

大致步骤如下：

要证明an = f(n).

1. 首先证明在初始条件下，a1 = f(1)；
2. 然后假设ak = f(k)成立，再证明ak+1 = f(k+1)成立。

完成以上两步就证得命题成立。

递归问题

an = n! = f(n),使用递归来求解阶乘的值。

1. 初始条件a1 = 1; 对应递归的结束条件if(n==1) return 1;
2. 假设ak = k!, 要求ak+1 = ak * (k+1) = f(k)*(k+1).

这里对应了程序中的f(k) = f(k-1)*k.

代码：

#include "stdio.h"

int f(int n);
void main() {
    int n;
    scanf("%d", &n);
    printf("n! = %d", f(n));
}

int f(int n) {
    if(n == 1) return 1;
    return f(n-1)*n;
}

输出结果：

 实现原理

        递归其实可以理解为函数嵌套的调用本身，所以本质还是函数调用的过程机制。如果想要知道函数是如何被调用的，在C语言层面是无法知晓的，从下图可以看到C语言作为一种高级语言，是用户通过用户接口从上至下地调用了系统方法从而实现了相关功能。所以要知道函数调用地机制需要下沉到操作系统地系统调用中来。

        系统嵌套调用是如何实现地呢？以下是摘自操作系统中地一段原话，大致意思是由AP和FP两个指针，指向本次系统调用地参数列表和数据项。当有新的系统调用发生，那么CPU环境和AP,FP指针会压入栈中，保存起来，CPU执行新的系统调用。执行完新的系统同调用后，然后返回栈中弹出地原系统调用地AP,FP等保存信息，继续之前地中断程序。 

非递归化

        了解了递归地原理之后，可以发现函数调用，或者说系统调用其实就是用栈来实现地，采用先进后出地方式，保存和取出调用回来返回值。

        所以非递归化首先需要申请一个栈，然后采用循环结构，f(n)中，如果n等于1了，循环终止，否则压入栈中保存起来。这里相当于系统调用过程中保存AP和FP指针地过程。

        然后从栈中逐个pop出元素来计算，得到最终地结果。这里可以理解为系统调用结束返回时返回到上次系统调用时，要取出保存地环境。

 递归代码：

void f(int n) {
    if(n == 0) {
        return ;
    } else {
        str[p++] = n%10 + '0';
        f(n/10);
    }
}

非递归代码：

void f1(int n) {
    while(n) {
        str[p++] = n%10 + '0';
        n = n/10; 
    }
}