【C语言】函数的系统化精讲（三）1

一、递归举例

.通过上回（【C语言】函数的系统化精讲（二））我们了解到递归的限制条件，递归在书写的时候，有2个必要条件：

递归在书写时有两个必要条件：

• 递归必须有一个限制条件，当满足该条件时，递归停止。

• 每次递归调用后，逼近该限制条件。

下面我们来进行递归举例，更加深刻了解一下吧！

二、递归举例

2.1求n的阶乘

计算n的阶乘（不考虑溢出），n的阶乘就是1~n的数字累积相乘。

分析：

我们知道n的阶乘的公式： n！ = n ∗ (n − 1)!

比如：

5！= 5 * 4 * 3 * 2 * 1

4! = 4 * 3 * 2 * 1

所以我们可以直接：5！=5* 4！

这样思考的话，我们就可以把一个大的问题，转换成一个规模较小，又与原问题相似问题来进行求解！

再稍微分析⼀下，当 n<=0 的时候，n的阶乘是1，其余n的阶乘都是可以通过上述公式计算。

n的阶乘的递归公式如下：

代码：

int Fact(int n)
{
  if (n <= 0)
    return 1;
  else
    return n * Fact(n - 1);
}
int main()
{
  int n = 0;
  scanf("%d", &n);
  int ret = Fact(n);
  printf("%d\n", ret);
  return 0;
}

当然，这里n的值不考虑太大的情况，n太大，会导致栈溢出，

2.2 顺序打印⼀个整数的每⼀位

输⼊⼀个整数m，打印这个按照顺序打印整数的每⼀位。

⽐如：

输⼊：1024 输出：1 0 2 4

输⼊：520 输出：5 2 0

分析：

首先，，我们看1024，怎么得到这个数的每⼀位呢？

1024%10就能得到4，然后1024/10得到102，这就相当于去掉了4

然后继续对102%10，就得到了2，再除10去掉2，以此类推

不断的 %10 和 \10 操作，直到1234的每⼀位都得到；

但是这⾥有个问题就是得到的数字顺序是倒着的

但是我们有了灵感，我们发现其实⼀个数字的最低位是最容易得到的，通过%10就能得到

那我们假设想写⼀个函数Print来打印n的每⼀位，如下表⽰：

Print(1024)
   |
   └── Print(102)
             |
             └── Print(10)
                       |
                       └── Print(1)
                                 |
                                 └── Print(0)

在这个示意图中，从最右边的数字开始，递归调用Print函数，每次都打印出当前数字的最后一位，然后将问题规模减小，直到数字变成0为止。具体的过程如下：

1. 调用Print(1024)。
2. Print(1024)调用Print(102)。
3. Print(102)调用Print(10)。
4. Print(10)调用Print(1)。
5. Print(1)调用Print(0)。
6. Print(0)直接返回，不做任何处理。
7. Print(1)返回，打印出1，然后返回到调用它的函数。
8. Print(10)返回，打印出0，然后返回到调用它的函数。
9. Print(102)返回，打印出2，然后返回到调用它的函数。
10. Print(1024)返回，打印出1，然后函数执行结束。
11. 11代码：

# define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>

void Print(int n)
{
  if (n > 9)
  {
    Print(n / 10);
  }
  printf("%d ", n % 10);
}
int main()
{
  int m = 0;
  scanf("%d", &m);
  Print(m);
  return 0;
}

三、递归与迭代

【C语言】函数的系统化精讲（三）2：https://developer.aliyun.com/article/1474658