高校问答我家的大明郡主停更:递归是怎么一回事?哪位老师能否通俗易懂的讲讲原理?
来源：百度文库 编辑：高校问答 时间：2024/05/04 12:54:49
哪位老师能否通俗易懂的讲讲原理?
递归通俗的讲就是一个函数在其代码中反复调用自身。你应该知道菲波纳契数列，这个数列的定义是
f(x)=1 (x=1)
f(x)=2 (x=2)
f(x)=f(x-1)+f(x-2) (x>2)
也就是说从第三项开始的每一项的值都等于是前两项之和。这在数学中叫递推数列--高中数学内容。
如果把它变为一个要求第n个菲波纳契数的代码的话，应该如下所示（为了避免语言不通：）我使用伪代码）：
int f(int step)
在这里x为上面所说的x变量，也就是要求的是第x项的值
{
if step=1
{
return 1
}
else if step=2
{
return 2
}
如果求得是第一项和第二项的话，就分别返回1和2，并退出函数
return f(x-1)+f(x-2)
否则的话就返回前面两项的和
}
这里的关键是最后一句。这里函数的返回直又要反过去调用它自身计算前面两项的值，这样就会反复调用，直到x变量在某次调用中变为1和2，返回已知的第一项和第二项的值，在层层返回，最后得出要求的第x项的值
说到本质的话，递归是一段程序的代码反复效用，把程序的参数等变量保存在一个堆栈里，直到到了边界条件以后再层层返回，将堆栈中的数据弹出计算，最后得到结果
补充一下，递规包括直接递规和间接递规。直接递规是指在代码中反复调用自身，而间接递规是间接地调用自身。
比如：
int g(int x);
int f(int x)
{
if( x<=0 )
return x ;
else
return g(x-1)+2 ;
}
int g(int x)
{
return f(x)*x ;
}