递归调用函数专题-C语言

0| 前言

本小节主要学习一种自己嵌套自己的函数调用方法——递归调用

1| 示例

例如，在给定整数n的情况下，计算并输入阶乘n!的程序。

阶乘函数的定义：

 int factorial(int n){
     int product;
     for (int i = 1; i <= n; i++){
         product = product * i;
     }
     return product;
 }

这个函数思想：使用了一个循环将1到n的数值依次相乘进行计算，并将得到的乘积作为结果返回。

用for循环解决问题

• 一个循环从1开始
• 一直不断相乘，直到乘以n为止

2| 递归思想求解阶乘

递归思想求解函数阶乘

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

其实换一个角度在思考这个问题，n!可以看成 n*(n-1)!的乘积， 而(n-1)!又可以看作是(n-1)*(n-2)!的乘积….. 以此类推到 2 * 1 ， 代码是不是更简洁一点呢？

其实，像这种在一个函数的定义中调用自身的情况被称为–递归调用

（1）头递归

例如定义的函数：

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

如果传入给函数factorial() 的n是5：

factorial(5) = 5 * factorial (4)

= 5 * 4 * factorial (3)

= 5 * 4 * 3 * factorial(2)

= 5 * 4 * 3 * 2 * factorial(1)

= 5 * 4 * 3 * 2 * 1

像这种返回一个包含本身函数的递归调用的这种递归设计，被称为投递归。

（2）尾递归

与头递归相对应的就是尾递归，尾递归的思想实现如下：

 int factorial(int n, int product){
     if (n == 0){
         return product;
     }
     product = product * n;
     return factorial(n-1, product);
 }

同样也拿 n=5, 来了解一下程序的实现细节：

 factorial (5,1)  ~ factorial(n, product * n)
 = factorial(4,1*5) = factorial(4, 5)
 = factorial(3, 5*4) = factorial(3, 20)
 = factorial(2, 20*3) = factorial(2, 60)
 = factorial(1, 60*2) = factorial(1, 120)]
 = factorial(0, 120*1) = factorial(0, 120)
 = 120  ~ product

小伙伴没有发现，尾递归的实现中，每一次函数递归调用都会将一个阶段性的结果传递到下一次被调用的函数中，当最终的一般终止条件满足时，把最终结果直接返回。