c语言递归的问题

递归就是调用自己的意思，而且你写错了，应该是return ans；返回值是自己，而不是0；比如说，实参传递形参给它n=2；

你如果觉得调用自己不明白的话，你就把上面的函数定义成：

fact1，fact2，fact3他们只是名字不一样，自定义函数的内容都是完全相同的。

然后自定义函数fact1开始运行：

n>0;成立，执行ans=nfact2（n-1）； //相当于ans=2fact2（n-1）；

ans这句语句调用fact2自定义函数，实参n-1=1传给fact2的形参。

n>0;成立，执行ans=fact3（n-1）； //这是n=1，形参收到的数据是1，1fact3（n-1）

实参n-1=0传给fact3的形参；

n>0不成立，直接ans=1。

之前都是调用的过程，下面是返回值

先是从fact3返回1，返回到fact2，

fact2中ans=11=1，这个值返回到fact1；

fact1中ans=21=2，这个值返回到主函数。

同理，如果n=5的话，相当于要写fact1，fact2……fact6这6个函数。

返回的结果是112345=120到主函数。

但是如果你把这六个函数都写出来，要浪费多少时间，既然他们的内容都是一样的，为什么不把名字定为1个，然后自己调用自己，这就形成了递归函数了。

递归函数相当于调用多次自定义函数，而每次调用的对象都是同一个，只是每次传递的参数发生了变化。

希望你多看几遍，不明白继续问，纯手写，望采纳。

函数的递归调用

递归问题是一个说简单也简单，说难也有点难理解的问题我想非常有必要对其做一个总结

首先理解一下递归的定义，递归就是直接或间接的调用自身而至于什么时候要用到递归，递归和非递归又有那些区别？又是一个不太容易掌握的问题，更难的是对于递归调用的理解下面我们就从程序+图形的角度对递归做一个全面的阐述

我们从常见到的递归问题开始:

1 阶层函数

#include <iostream>

using namespace std;

int factorial(int n)

{

if (n == 0)

{

return 1;

}

else

{

int result = factorial(n-1);

return n result;

}

}

int main()

{

int x = factorial(3);

cout << x << endl;

return 0;

}

这是一个递归求阶层函数的实现。很多朋友只是知道该这么实现的，也清楚它是通过不断的递归调用求出的结果但他们有些不清楚中间发生了些什么下面我们用图对此做一个清楚的流程:

根据上面这个图，大家可以很清楚的看出来这个函数的执行流程。我们的阶层函数factorial被调用了4次并且我们可以看出在调用后面的调用中，前面的调用并不退出。他们同时存在内存中。可见这是一件很浪费资源的事情。我们该次的参数是3如果我们传递10000呢。那结果就可想而知了肯定是溢出了就用int型来接收结果别说10000，100就会产生溢出即使不溢出我想那肯定也是见很浪费资源的事情我们可以做一个粗略的估计:每次函数调用就单变量所需的内存为:两个int型变量n和result在32位机器上占8B那么10000就需要10001次函数调用共需100018/1024 = 78KB这只是变量所需的内存空间其它的函数调用时函数入口地址等仍也需要占用内存空间。可见递归调用产生了一个不小的开销

2 斐波那契数列

int Fib(int n)

{

if (n <= 1)

{

return n;

}

else

{

return Fib(n-1) + Fib(n-2);

}

}

这个函数递归与上面的那个有些不同每次调用函数都会引起另外两次的调用最后将结果逐级返回

我们可以看出这个递归函数同样在调用后买的函数时，前面的不退出而是在等待后面的结果，最后求出总结果。这就是递归

3

#include <iostream>

using namespace std;

void recursiveFunction1(int num)

{

if (num < 5)

{

cout << num << endl;

recursiveFunction1(num+1);

}

}

void recursiveFunction2(int num)

{

if (num < 5)

{

recursiveFunction2(num+1);

cout << num << endl;

}

}

int main()

{

recursiveFunction1(0);

recursiveFunction2(0);

return 0;

}

运行结果:

0

1

2

3

4

4

3

2

1

0

该程序中有两个递归函数。传递同样的参数，但他们的输出结果刚好相反。理解这两个函数的调用过程可以很好的帮助我们理解递归:

我想能够把上面三个函数的递归调用过程理解了，你已经把递归调用理解的差不多了并且从上面的递归调用中我们可以总结出递归的一个规律：他是逐级的调用，而在函数结束的时候是从最后面往前反序的结束这种方式是很占用资源，也很费时的。但是有的时候使用递归写出来的程序很容易理解，很易读

为什么使用递归:

1 有时候使用递归写出来的程序很容易理解，很易读

2 有些问题只有递归能够解决非递归的方法无法实现如:汉诺塔

递归的条件:

并不是说所有的问题都可以使用递归解决，他必须的满足一定的条件。即有一个出口点也就是说当满足一定条件时，程序可以结束，从而完成递归调用，否则就陷入了无限的递归调用之中了并且这个条件还要是可达到的

递归有哪些优点:

易读，容易理解，代码一般比较短

递归有哪些缺点:

占用内存资源多，费时，效率低下

因此在我们写程序的时候不要轻易的使用递归，虽然他有他的优点，但是我们要在易读性和空间，效率上多做权衡一般情况下我们还是使用非递归的方法解决问题若一个算法非递归解法非常难于理解。我们使用递归也未尝不可如:二叉树的遍历算法非递归的算法很难与理解而相比递归算法就容易理解很多

对于递归调用的问题，我们在前一段时间写图形学程序时，其中有一个四连同填充算法就是使用递归的方法。结果当要填充的图形稍微大一些时，程序就自动关闭了这不是一个人的问题，所有人写出来的都是这个问题当时我们给与的解释就是堆栈溢出。就多次递归调用占用太多的内存资源致使堆栈溢出，程序没有内存资源执行下去，从而被 *** 作系统强制关闭了这是一个真真切切的例子。所以我们在使用递归的时候需要权衡再三

递归其实就是“一个函数的自调用”

在这个“自调用”的过程中，必须要有一个变化的“参数”，当这个“参数”达到你的期望值的时候，终止该“自调用”过程

拿楼主的程序来说

demo($n)内部又有调用demo($n-1)，构成了“自调用”

且，$n又有一个“期望值”，即是$n>1，不满足此条件时，该自调用终止

即是说，最后一个执行的demo是demo($n9-1)，其中$n9=2，然后返回为1（因为执行了return 1）

则$n9demo($n9-1)即等于 2demo(2-1)，又等于21=2;

则$n8demo($n8-1)即等于 3demo(3-1)，又等于32=6;

则$n7demo($n7-1)即等于 4demo(4-1)，又等于46=24;

……

依次类推

这样想：

demo(1)是等于1，这个没有疑问吧？

然后demo(2)等于2demo(1)=21=2

然后demo(3)等于3demo(2)=32=6

……

一直到demo(10)

这个程序是用来实现几个数的相加（我的理解），最后一个输出是加法的最终结果。

首先用我的语言解释一下递归的意义。递归算法就像是一些嵌套的屋子，每一层屋子里都有一个你想拿到的东西，你从最外层的门开始进去，但是你进的时候并不取走东西，而是等到你到达最里面的屋子时，取出这个最里面的东西，并开始往外走，到次里层屋子取出东西，继续往外走，重复这个动作，一直到你取出最外面屋子里的东西并跳出整个屋子。

下面针对你的程序用上面的思想来解释一下：

现在你要实现几个数的和，你每一次输入的数字相当于进入下一层屋子的钥匙。第一次输入的是1，你进到第一层，把1先存在这里，并不作加法，第二次输入2，进到第二层，把2放在这一层，然后输入3，进入第三层，把3放在这里，最后输入0，你进入了最里面的屋子，此时执行了

if(x==0) sum=0; //else 就不执行了，所以也没有后续的test(sum)

cout<<sum<<endl; //这时第一次输出sum,为0。

现在从最里面该往外走了，首先到了第三层，这里有你存着的数字3，现在，把刚才得到的sum=0与3相加，得到了sum=3,并输出。

再往外走，用sum=3和这里存的2相加，得到sum=5，并输出。

最后一层，肯定就得到了6。

这样讲解不知道你明白了没有？希望对你有帮助！

return; 返回调用点；

非递归，返回调用他的那个函数，调用他的那个地方；

递归调用，返回自己调用自己的地方，或者第一次调用他的地方，这个只有分析代码才知道具体情况。

无返回值函数，相当于，BASIC 的子程序，pascal 的过程，返回调用语句处，以便执行下一条语句，实际返回点是下一条指令，然后可能还要，再执行些，调用后的扫尾的工作，才来到下一步执行。

有返回值函数，返回使用函数值的地方。

不管哪一种，都是返回调用处，继续向下执行。

函数调用，首先要执行计算参数的任务，然后执行参数传递的工作，然后才轮到调用函数。

函数调用前，可能还要保存现场，具体就是寄存器压栈保存，防止函数调用时，现场被破坏

调用完成，要恢复现场，恢复寄存器的值，具体就是从堆栈中，d出保存的寄存器数据值。

递归函数，一般包含：

1）退出条件，适当条件下函数退出递归。

2）递归部分（自调用，并适当更新，执行条件，函数参数，全局变量等）

3）执行部分，如打印节点信息等。

看递归代码，

1）首先，看何时退出递归（程序不再执行自调用）

2）看递归执行顺序

3）看执行代码，干了什么。和递归部分的执行的先后顺序。

4）有些递归函数，没有独立的执行部分，只有一些表达式，看他先后执行那些表达式。

5）有些递归函数，只看函数本身看不出是递归函数，因为这个函数，会调用别的函数，别的函数又会再回头调用该函数本身。

这就要查看，函数调用链，里面是否调用了自己。

PS：

不管是否递归，函数总是要干点什么的（函数的功能）。

所以，看递归函数，不能光看函数，自己调用自己的，递归部分；

还要看，非递归部分干了什么，这个部分，才是递归实际干的事情；

递归不过是一种重复而已，通过递归部分反复调用自己；

从而重复执行非递归部分，完成递归函数的功能。

C,C++ ：return 语句有两个功能

1）返回调用处，程序执行下一步。

2）返回执行的结果

1）这个功能，返回的函数调用的位置，执行下步的程序。

在表达式中，函数调用会得到一个结果，程序解析表达式的时候遇到函数，会调用函数

代码执行，会因此跳到函数内部，开始执行函数内部的程序，执行完毕；

会得到一个结果，这个结果就是函数的返回值，也叫函数值，

这时函数调用就结束了，程序返回继续解析表达式，并用函数返回值代替函数，继续解析（计 算）表达式。

1） 如果表达式比较复杂的话；如果表达式解析没有完成，函数返回解析表达式的断点处，

如果完成了，执行下一条语句，

2）如果表达式比较简单，函数返回后，会执行下一条语句。

单独的一条函数调用，称为函数调用表达式。

所以，C 几乎一切都是表达式。

任何表达式，加上分号，就是一条语句。

所以 单独的函数调用加上分号，构成一条单独的函数调用表达式语句，就是函数调用语句。

函数调用语句，执行完成后返回调用点，执行逻辑上的下一条语句。

总结：

函数返回

1）返回值：函数返回值，放在特定的寄存器中（

X86，WINDOWS WIN32 VC eax---char,int 指针; edx:eax---long long,__int64;协处理器的浮点堆栈寄存器 float,double,long double :ST(0) ），如果返回值的类型，比较长，会使用一个全局变量（static？？？）存放返回值，并把该全局变量的指针，放在特定的寄存器中(X86，WINDOWS WIN32 VC：

eax)。

2）返回位置：函数结束，程序返回调用点。继续执行。

注意：由于函数可以用在表达式中，所以函数实际返回，解析表达式的断点处，继续解析表达式。

函数调用本身，就是一个表达式，称为函数调用表达式。