我们先来了解下栈帧的概念，帮助更好的理解递归和尾递归的区别。
一、栈帧的概念
栈帧（Stack Frame），也被称为活动记录（Activation Record），是程序执行过程中，每次函数调用时创建的一个数据结构。栈帧用于存储函数调用期间所需的所有信息，包括但不限于：
- 局部变量：函数内部定义的变量。
- 参数：传递给函数的参数。
- 返回地址：函数完成执行后，程序应继续执行的代码位置。
- 临时变量：编译器为了优化或实现语言特性而产生的临时变量。
- 保存的寄存器值：某些情况下，需要保存当前CPU寄存器的状态，以便在函数返回时恢复。
每当一个函数被调用时，一个新的栈帧就会被压入调用栈（Call Stack）。调用栈是一个后进先出（LIFO, Last In First Out）的数据结构，意味着最近被调用的函数会最先从栈中弹出。
当函数执行完毕并返回时，对应的栈帧会被从调用栈中移除，同时控制权和相关状态会恢复到调用该函数的地方。
二、递归和尾递归的详细深度剖析
递归和尾递归都是调用函数本身来进行计算。
1、递归
递归是层层往下深入到最底层，再由最底层逐级往上返回值。
例如：求n的阶乘问题。
#include <stdio.h>
//核心代码
unsigned long factorial(unsigned int n) {if (n == 0) {return 1;} else {return n * factorial(n - 1);}
}int main() {unsigned int number = 5;printf("Factorial of %u is %lu\n", number, factorial(number));return 0;
}求5！的递归过程
5 * factorial ( 4 )
4 * factorial ( 3 )
3 * factorial ( 2 )
2 * factorial ( 1 )
我们知道，一个函数的完整结束，需要执行完成最后一条语句。
可以看到，要求5的阶乘，整个factorial函数的返回值是5 * factorial ( 4 )的值，也就是说只有求出5 * factorial ( 4 )的值整个程序才算结束。
而要求出5 * factorial ( 4 )的值，我们需要先知道factorial ( 4 )的值。于是，程序就会先调用factorial函数递归去求出factorial ( 4 )的值，这时，我们要知道5 * factorial ( 4 )还没有被完全执行完成，那么，我们就需要记录下当前执行到5 * factorial ( 4 )这个位置，以便后续完成factorial ( 4 )函数的调用，求出factorial ( 4 )的值时，程序可以重新从这个位置继续执行5 * factorial ( 4 )的值求得最终的结果并返回，结束整个函数。
而栈帧就能存储函数完成执行后，程序应继续执行的代码位置。
而根据上面求5！的递归过程，可以知道，我们需要记录4个程序当前执行到的位置，也就是有4个栈帧要被压入调用栈。（因为factorial ( 4 ) = 4 * factorial ( 3 )，需要知道factorial ( 3 )的值，先用一个新的栈帧记录下当前执行的位置，再去调用factorial ( 3 )，后面以此向下类推）
直到最后调用factorial ( 1 )，return 1，factorial ( 1 )的函数调用完整结束。于是，回到factorial ( 1 )对应的栈帧记录的位置继续执行程序，同时把factorial ( 1 )对应的栈帧从调用栈中移除，以此往上类推回到5 * factorial ( 4 )，完整结束5的阶乘的计算。
通过整个递归过程，我们可以知道，每一次递归都有一个新的栈帧被压入调用栈。可想而知，当递归深度较大时，可能会导致栈溢出错误。
2、尾递归
尾递归是一种特殊的递归形式。尾递归是层层往下深入到最底层，最底层的结果即为最终结果。不再需要由最底层逐级往上返回值。
而尾递归与递归最大的区别在于：只会在首次调用尾递归函数时创建一个新的栈帧。
当函数再调用自己时，不会创建新的栈帧。相反，它会更新当前栈帧中的参数和其他相关信息，然后跳转到函数的开头继续执行。
为什么呢？我们还是用求n的阶乘问题来举例。
#include <stdio.h>
//核心代码
unsigned long factorial_tail_recursive(unsigned int n, unsigned long accumulator) {if (n == 0) {return accumulator;} else {return factorial_tail_recursive(n - 1, n * accumulator);}
}unsigned long factorial(unsigned int n) {return factorial_tail_recursive(n, 1);// 初始调用时，累加器设为1
}int main() {unsigned int number = 5;printf("Factorial of %u is %lu\n", number, factorial(number));return 0;
}求5！的递归过程
factorial_tail_recursive( 4 , 5 * 1)
factorial_tail_recursive( 3 , 4 * 5)
factorial_tail_recursive( 2 , 3 * 20)
factorial_tail_recursive( 1 , 2 * 60)根据下面这段代码，
return factorial_tail_recursive(n - 1, n * accumulator);我们可以知道，递归调用是函数执行的最后一个操作，并且其返回值直接作为整个函数的返回值。
也就是说当我们调用factorial_tail_recursive( 5 )时，首次调用factorial_tail_recursive函数，创建了一个新的栈帧，然后进入到factorial_tail_recursive函数中执行，直到执行到调用factorial_tail_recursive( 4 , 5 * 1)，直接return，factorial_tail_recursive( 4 , 5 * 1)的结果即为最终结果（也就是最深层factorial_tail_recursive( 1 , 2 * 60)递归调用的结果），这时factorial_tail_recursive( 5 , 1)整个函数调用完整执行完成。不像递归那样，每层递归还需要再乘以n（尾递归是把乘以n这一步作为递归参数直接传给下一次递归调用），再把值往上返回。也正因为不需要往上返回值，我们才不需要保存当前的栈帧来记录程序执行到的位置。
于是执行调用的factorial_tail_recursive( 4 , 5 * 1)、factorial_tail_recursive( 3 , 4 * 5)、factorial_tail_recursive( 2 , 3 * 20)、factorial_tail_recursive( 1 , 2 * 60)时，我们只需要重用首次创建的栈帧并更新栈帧的信息即可，不需要再创建新的栈帧。
避免了随着递归深度增加而不断增长的调用栈，从而节省了内存空间，并允许处理更深的递归层级而不导致栈溢出。
