C语言递归的那点事

发表于 | 分类于
字数统计: 957 | 阅读时长 ≈ 4

浅析递归

​ 递归是一种绝大多数语言都支持的编程方式。但是我本人并不建议使用。

1.是什么？

1.1 释义

​ 允许函数循环调用自己的过程

1.2 原理

  1. 每级函数调用都有自己的变量
  2. 每次函数调用都会返回一次
  3. 递归函数中位于递归调用之前的语句顺序执行
  4. 递归函数中位于递归调用之后的语句逆序执行
  5. 每级递归都有自己的变量，但并不会拷贝函数代码
  6. 递归函数必须有让递归调用停止的语句，否则将无限递归

2.为什么？

2.1 优点

​ 递归的代码简洁优雅。繁杂的执行过程交由操作系统辅助解决。

2.2 缺点

​ 相较于其优点，缺点更加显而易见，由于函数每次递归调用自己时，操作系统都要为其保留函数的运行现场（俗称系统栈），这种系统级的开销会浪费较多的资源，因而代码的效率并不高。而且还不方便人们的阅读，难以理解。

3.怎么做？

Talk is cheap,show you the code.

3.1 普通递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/*
    ——《C Primer Plus》p595
    函数执行过程：
    1.主函数调用up_and_down(), 并传递参数 1 ;
    2.开始执行up_and_down(), 接受参数 1 ;
    3.(#1)输出参数 n == 1 , 以及参数 n == 1 的地址
    4.进行if判断, n == 1 < 4, 再次调用up_and_down(), 并传递参数 2,与此同时，保留函数第一次执行的运行现场;
    5.进行第一次递归:
        1.(#1)输出参数 n == 2 , 以及参数 n == 2 的地址
        2.进行if判断, n == 2 < 4, 再次调用up_and_down(), 并传递参数 3,与此同时，保留函数第二次执行的运行现场;
        3.进行第二次递归:
            1.(#1)输出参数 n == 3 , 以及参数 n == 3 的地址
            2.进行if判断, n == 3 < 4, 再次调用up_and_down(), 并传递参数 4,与此同时，保留函数第三次执行的运行现场;
            3.进行第三次递归:
                1.(#1)输出参数 n == 4 , 以及参数 n == 4 的地址
                2.进行if判断, n == 4 < 4, 不满足if条件，不执行if内的语句
                3.(#2)输出参数 n == 4 , 以及参数 n == 4 的地址
            4.回归第三次的执行现场
            5.(#2)输出参数 n == 3 , 以及参数 n == 3 的地址
        4.回归第二次的执行现场
        5.(#2)输出参数 n == 2 , 以及参数 n == 2 的地址
    4.回归第一次的执行现场
    5.(#2)输出参数 n == 1 , 以及参数 n == 1 的地址
    6.up_and_down()执行完毕, 回归main()
    7.return 0.
    8.main()执行完毕
*/

#include <stdio.h>
void up_and_down(int);
int main(void)
{
    up_and_down(1);
    return 0;
}
void up_and_down(int n)
{
    printf("Level %d: n location %p\n", n, &n); //#1
    if (n < 4)
        up_and_down(n + 1);
    printf("LEVEL %d: n location %p\n", n, &n); //#2
}

3.2 尾递归

递归调用在主函数的return语句之前。尾递归形式简单，相当于循环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <stdio.h>
long fact(int n);
long rfact(int n);
int main(void)
{
    int num;
    printf("This program calculates factorials.\n");
    printf("Enter a value in the range 0-12 (q to quit):\n");
    while (scanf("%d", &num) == 1)
    {
        if (num < 0)
            printf("No negative numbers, please.\n");
        else if (num > 12)
            printf("Keep input under 13.\n");
        else
        {
            printf("recursion: %d factorial = %ld\n", num, fact(num));
            printf("recursion: %d factorial = %ld\n", num, rfact(num));
        }
        printf("Enter a value in the range 0-12 (q to quit):\n");
    }
    printf("Bye.\n");
    return 0;
}
long fact(int n)
{
    long ans;
    for (ans = 1; n > 1; n--)
    {
        ans *= n;
    }
    return ans;
}
long rfact(int n)
{
    long ans;
    if (n > 0)
        ans = n * rfact(n - 1);
    else
        ans = 1;
    return ans;
}