C允许函数调用它自己，这种调用过程称为递归。可以使用循环的地方通常都可以使用递归。有时用循环解决问题比较好，但有时用递归更好。递归方案更简洁，但效率却没有循环高。以下是一个递归的示例：

#include <stdio.h>

void go(int);

int main(void) {
    go(1);
    system("pause");
    return 0;
}

void go(int n) {
    printf("Sentence1 : Level %d and n location %p\n", n, &n);
    if (n < 4)
        go(n + 1);
    printf("Sentence2 : Level %d and n location %p\n", n, &n);
}

运行结果为：

Sentence1 : Level 1 and n location 0061ff20
Sentence1 : Level 2 and n location 0061ff00
Sentence1 : Level 3 and n location 0061fee0
Sentence1 : Level 4 and n location 0061fec0
Sentence2 : Level 4 and n location 0061fec0
Sentence2 : Level 3 and n location 0061fee0
Sentence2 : Level 2 and n location 0061ff00
Sentence2 : Level 1 and n location 0061ff20

以上代码中，递归的工作流程为：

1. main()函数调用go()函数，参数为1。go()执行Sentence1的打印，打印Leve 1和n当前的存储地址。

2. 由于n（当前为1）小于4，递归调用go()自身，参数为n+1，即1+1。go()执行Sentence1的打印，打印Leve 2和n当前的存储地址。

3. 由于n（当前为2）小于4，递归调用go()自身，参数为n+1，即2+1。go()执行Sentence1的打印，打印Leve 3和n当前的存储地址。

4. 由于n（当前为3）小于4，递归调用go()自身，参数为n+1，即3+1。go()执行Sentence1的打印，打印Leve 4和n当前的存储地址。

5. 由于n（当前为4）不再小于4，执行Sentence2的打印，打印Leve 4和n当前的存储地址。完成后把控制流返回上一级调用函数，即n为3时的go()函数。

6. go()函数从递归调用自身的下一条语句继续执行，即执行Sentence2的打印，打印Leve 3和n当前的存储地址。完成后把控制流返回上一级调用函数，即n为2时的go()函数。

7. go()函数从递归调用自身的下一条语句继续执行，即执行Sentence2的打印，打印Leve 2和n当前的存储地址。完成后把控制流返回上一级调用函数，即n为1时的go()函数。

8. go()函数从递归调用自身的下一条语句继续执行，即执行Sentence2的打印，打印Leve 1和n当前的存储地址。完成后把控制流返回main()函数。

注意：每级递归的变量n都属于本级递归函数私有，从程序打印的地址值就可以看出，对于Level值相同的打印，Sentence1和Sentence2中的n的地址是一样的，即它们就是同一个变量n。

递归基本原理的重点内容如下：

• 每级函数调用都有自己的变量。第1级的n和第2级的n不同，以上程序中共创建了4个单独的变量，每个变量名都是n，但是它们的值各不相同。当程序最终返回go()的第1级调用时，最初的n仍然是它的初值1。

• 每次函数调用都会返回一次。当本级递归调用函数执行完毕后，控制权将被传回上一级递归。程序必须按顺序逐级返回递归，不能跳级。

• 递归函数中位于递归调用之前的语句，均按被调用函数的顺序执行。例如：打印Sentence1的语句按照Level 1~4的顺序打印。

• 递归函数中位于递归调用之后的语句，均按被调用函数相反的顺序执行。例如：打印Sentence2的语句按照Level 4~1的顺序打印。

• 虽然每级递归都有自己的变量，但是并没有拷贝函数的代码。程序按顺序执行函数中的代码，而递归调用就相当于又从头开始执行函数的代码。除了为每次递归调用创建变量外，递归调用非常类似于一个循环语句。

• 递归函数必须包含能让递归调用停止的语句。通常，递归函数都使用if语句或其他等价的测试条件在函数形参等于某个特定值时终止递归。所以，递归调用的形参总是可变的。
  

最简单的递归形式是把递归调用置于函数的末尾，即正好在return语句之前，这种形式的递归称为尾递归。以下是一个分别使用循环和尾递归计算阶乘的示例：

#include <stdio.h>

long fact(int);//循环函数声明
long rfact(int);//递归函数声明

int main(void) {
    int number;
    printf("This program calculates factorials.\n");
    printf("Please enter a value in the range 0-12 (q to quit):\n");
    while (scanf("%d", &number) == 1) {
        if (number < 0)
            printf("No negative numbers,please.\n");
        else if (number > 12)
            printf("keep input under 13.\n");
        else {
            printf("loop: %d factorial = %ld\n", number, fact(number));
            printf("recursion: %d factorial = %ld\n", number, rfact(number));
        }
        printf("Please enter a value in the range 0-12 (q to quit):\n");
    }
    printf("Done.\n");
    system("pause");
    return 0;
}

//循环函数定义
long fact(int n) {
    long answer;
    for (answer = 1; n > 1; n--)
        answer *= n;
    return answer;
}

//递归函数定义
long rfact(int n) {
    long answer;
    if (n > 0)
        answer = n * rfact(n - 1);
    else
        answer = 1;
    return answer;
}

运行结果为：

This program calculates factorials.
Please enter a value in the range 0-12 (q to quit):
6
loop: 6 factorial = 720
recursion: 6 factorial = 720
Please enter a value in the range 0-12 (q to quit):
12
loop: 12 factorial = 479001600
recursion: 12 factorial = 479001600
Please enter a value in the range 0-12 (q to quit):
-5
No negative numbers,please.
Please enter a value in the range 0-12 (q to quit):
13
keep input under 13.
Please enter a value in the range 0-12 (q to quit):
q
Done.

以上代码中，使用递归的输出和使用循环的输出相同。一般而言，选择循环比较好，因为：

• 首先，每次递归都会创建一组变量，所以递归使用的内存更多，递归调用的数量受限于内存空间。

• 其次，由于每次函数调用要花费一定时间，所以递归的执行速度较慢。
  

递归在处理倒序时非常方便，比使用循环要简单。例如编写一个程序将十进制正整数转换为二进制数：

#include <stdio.h>

void to_binary(unsigned long);

int main(void) {
    unsigned long number;
    printf("Please enter an integer (q to quit):\n");
    while (scanf("%lu", &number) == 1) {
        printf("Binary equivalent: ");
        to_binary(number);
        putchar('\n');
        printf("Please enter an integer (q to quit):\n");
    }
    printf("Done.\n");
    system("pause");
    return 0;
}

void to_binary(unsigned long n) {
    long r;
    r = n % 2;
    if (n >= 2)
        to_binary(n / 2);
    putchar(r == 0 ? '0' : '1');
    return;
}

运行结果为：

Please enter an integer (q to quit):
8
Binary equivalent: 1000
Please enter an integer (q to quit):
255
Binary equivalent: 11111111
Please enter an integer (q to quit):
1024
Binary equivalent: 10000000000
Please enter an integer (q to quit):
q
Done.

在转换计算中，通过取模运算可以获得当前位上应当打印的值，二进制数的求值顺序与打印顺序正好相反，因此，在递归函数中，算法的设计就是先获得当前位应打印的值，再递归，最后打印当前位的值。