递归算法使用较小的输入值调用自身，并通过对较小输入的返回值执行基本操作来返回当前输入的结果。通俗地讲，递归算法是将问题拆分成多个子问题，通过优先更容易被处理的子问题，来解决完整问题。
要构建递归算法，需要将给定的问题陈述分成两部分。第一个是基本情况，第二个是递归步骤。
基本情况：是问题的最简单实例，由终止递归函数的条件组成，在满足给定条件时评估结果。
递归步骤：它通过对同一函数进行递归调用来计算结果，但输入的大小或复杂性会降低。
不同类型的递归
有四种不同类型的递归算法。
直接递归
如果函数在其函数体中重复调用自身，则称为直接递归。为了更好地理解这个定义，请查看直接递归程序的结构。
int fun(int z){
fun(z-1);}
间接递归
函数通过另一个函数调用自身的递归称为间接递归。
间接递归程序结构。
int fun1(int z)
{
int fun2(int y
{
fun2(z-1);
fun1(y-2);
}
}尾递归
如果递归调用是函数最后一次执行，则称递归函数是尾递归的。
int fun(int z)
{
printf(“%d”,z);
fun(z-1);
}无尾递归
如果递归调用不是函数完成的最后一件事，则称递归函数是非尾递归的。
int fun(int z)
{
fun(z-1);
printf(“%d”,z);
}递归方法的内存分配
每个递归调用都会在堆栈内存上生成一个新的函数副本。一旦返回一些数据，副本就会从存储中删除。每个递归调用都维护一个单独的堆栈，因为函数内部定义的所有参数和其他变量都保存在堆栈上。返回相关函数的值后，堆栈被删除。
递归在解析和监控每个递归调用的值方面非常复杂。因此，必须维护堆栈并跟踪其中指定的变量的值。
