【C语言】——尾递归

大家好，欢迎来到IT知识分享网。

一、 什么是尾递归

1.1、 尾递归是什么

  尾递归是指一个递归函数在调用自身时，该递归调用是函数的最后一条语句。换句话说，函数在调用自身之后不再执行任何操作，而是直接返回递归调用的结果。这种特殊形式的递归称为尾递归。

  尾递归对于编译器优化非常重要，因为编译器可以将尾递归优化为循环结构，从而避免递归调用过深导致栈溢出的问题。在使用递归解决问题时，如果能够确保递归调用是尾递归，那么可以提高程序的效率和性能。

1.2、 举例理解尾递归

  我们来看个例子：

void fn(int n) { 
    if (n > 0) printf("%d", n); return fn(n - 1); } 

  上数函数就是一个尾递归，因为return fn(n - 1);它的递归调用，是最后一个语句

  如果将函数最后一句改为：

return n * fn(n - 1); 

  那它还是不是尾递归呢？ 不是！
  
  因为函数在执行调用自身的指令后，还要执行 $\ast n$ 的操作，并没有直接返回递归调用的结果，所以并不是尾递归。

  同时，我们发现，该语句只有当 fn(n - 1) 的值回归后，才能执行 $\ast n$ 指令，即回归时调用。
  而尾递归所有语句都是在递推的时候调用，而不是回归时调用。

二、 递归与尾递归的转化

  下面，我们直接上题目：计算 $n$ 的阶乘

2.1、 递归方法

#include<stdio.h> //递归函数 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 = 0; ret = Fact(n); printf("%d\n", ret); return 0; } 

  该方法的深入讲解可以阅读《【C语音】——函数递归》 ，这里就不再赘述

2.2、 尾递归方法

解题思路：
  
  尾递归是递归的一种，我们初学可以在上面递归方法的代码基础上修改为尾递归。

return n * Fact(n - 1); 

  须改为：

return Fact(n - 1); 

修改如下：

int Fact(int n, int sum) { 
     if (n == 0) return 1; else return Fact(n - 1, n * sum); } 

（3）

  最后我们须将返回值 1 改为 sum ，不然不管输入什么值结果都是 1 ，那就尴尬了。
  这时，我们的函数调用 ret = Fact(n); 也要改为 ret = Fact(n, 1);

#include<stdio.h> int Fact(int n, int sum) { 
    if (n == 0) return sum; else return Fact(n - 1, n * sum); } int main() { 
    int n = 0; scanf("%d", &n); int ret = 0; ret = Fact(n, 1); printf("%d\n", ret); return 0; } 

三、 练习：用尾递归完成斐波那契数列

#include<stdio.h> int Fib(int n, int last_last, int last) { 
    if (n <= 2) return last; else return Fib(n - 1, last, last + last_last); } int main() { 
    int n = 0; scanf("%d", &n); int ret = 0; ret = Fib(n, 1, 1); printf("%d\n", ret); return 0; } 

图示：

  好啦，本期关于尾递归就介绍到这里啦，希望本期博客能对你有所帮助，同时，如果有错误的地方请多多指正，让我们在C语言的学习路上一起进步！