在什么情况下可以用递归解决问题?在写递归程序时的原则

1.当某个特性可以被重复执行时，就可以用递归来解决。使用递归某些时候可物锋以减少一些代码量。比如编程题里常见的一道题，求斐波拉切数列：

public static int feibolaqie(int num)

        {

            if (num < 3)//若num的值为1或2，则返回1

      蔽早      {

                return 1

            }

            else

            {

            宏蚂雀    return feibolaqie(num - 1) + feibolaqie(num - 2)

            }

        }

该函数作用是求出并返回第num位的斐波拉契数列的值。这里面就用到了递归。如果采用常规逻辑来做这道题，要写的代码就得多一些。

2.在写递归时要注意的原则就是，必须让递归函数有结束的机会。如果没有添加任何条件阻止递归的循环，那么就会无限执行下去。

3.日常开发中用递归的可能性很小，当然偶尔搞一搞也是可以。但必须注意不能写错而影响系统运行，另外一定要写上注释，让以后自己和其他开发者都能明白该递归函数的功能。

你的递归程序是错的，我转来个对的，带讲解的，你看看。

语言函数的递归和调用

一、基本内容：

C语言中的函数可以递归调用，即：可以直接（简单递归）或间接（间接递归）地自己调自己。激首猛

要点：

1、C语言函数可以递归调用。

2、可以通过直接或间接两种方式调用。目前只讨论直接递归调用。

二、递归条件

采用递归方法来解决问题，必须符合以下三个条件：

1、可以把要解决的问题转化为一个新问题，而这个新的问题的解决方法仍与原来的解决方法相同，只是所处理的对象有规律地递增或递减。

说明：解决问题的方法相同，调用函数的参数每次不同（有规律的递增或递减），如果没有规律也就不能适用递归调用。

2、可以应用这个转化过程使问题得到解决。

说明：使用其他的办法比较麻烦或很难解决，而使用递归的方法可以很好地解决问题。

3、必定要有一个明确的结束递归的条件。

说明：一定要能够在适当的地方结束递归调用。不然可能导致系统崩溃。

三、递归实例

例：使用递归的方法求n!

当n>1时，求n!的问题可以转化为n*(n-1)!的新问题。

比如n=5：

第一部分：5*4*3*2*1

n*(n-1)!

第二部分：4*3*2*1

(n-1)*(n-2)!

第三部分：3*2*1

(n-2)(n-3)!

第四部分：2*1

(n-3)(n-4)!

第五部分：1

（n-5）!

5-5=0，得到值1，结束递归。

源程序：

fac(int

n)

{int

t

if(n==1)||(n==0)

return

1

else

{

t=n*fac(n-1)

return

t

}

}

main(

)

{int

m,y

printf(“Enter

m:”)

scanf(“%d”,&m)

if(m<0)

printf(“Input

data

Error!\n”)

else

{y=fac(m)

printf(“\n%d!

=%d

\n”,m,y)

}

}

四、递归说明

1、当函数自己调用自己时，系统将自动把函数中当前的变量和形参暂时保留起来，在新一轮的调用过程中，系统为新调用的函数所用到的变量和形参开辟另外的存储单元（内存空间）。每次调用函数所使用的变量在不同的内存空间。

2、递归调用的层次越多，同名变量的占用的存储单元也就越多。一定要记住，每次函数的调用，系统都会为该函数的变量开辟新的内存空间。

3、当本次调用的函数运行结束时，系统将释放本次调用时所占用的内存空间。程序的流程返回到上一层的调用点，同时取得当初明桥进入该层时，函数中的变量和形参所占用的内存空间的数据。

4、所有递归问题都可以用非递归的方法来解决，但对于一些比较复杂的递归问题用非递归的方法往往使程序变得十分复杂难以读懂，而函数的递归调用在解芹携决这类问题时能使程序简洁明了有较好的可读性；但由于递归调用过程中，系统要为每一层调用中的变量开辟内存空间、要记住每一层调用后的返回点、要增加许多额外的开销，因此函数的递归调用通常会降低程序的运行效率。

五、程序流程

fac(int

n)

/*每次调用使用不同的参数*/

{

int

t

/*每次调用都会为变量t开辟不同的内存空间*/

if(n==1)||(n==0)

/*当满足这些条件返回1

*/

return

1

else

{

t=n*fac(n-1)

/*每次程序运行到此处就会用n-1作为参数再调用一次本函数,此处是调用点*/

return

t

/*只有在上一句调用的所有过程全部结束时才运行到此处。*/

}

}

本人学c++，c的语法已经淡忘了，但是递归不管什么语言都是一毕慎裂个原理

其实简单一点来说就像数学里面的数列的通项公式：

例如一个数列是2，4，6，8，10......

很容易就可以得到通项公式是a[n]=2*n n是大于0的整数手闭

你肯定学过这个数列的另外一种表示方式就是： a[1]=2, a[n]=a[n-1]+2 n是大于1的整数

其实这就是一个递归的形式，只要你知道初始项的值，未知项和前几项之间的关系就可以知道整个数列。

程序例子：比如你要得到第x项的值

普通循环：

for(int i=1i<=ni++)

if (i == x)

cout <<2*i/*cout 相当于 c里面的printf,就是输出.*/

递归：

int a(int x) {

if (x = 1)

return 2/* 第一项那肯定是2了，这个也是递归的终止条件！ */

else return a(x-1)+2/* 函数自身调用自身是递归的一个特色 */

比如x=4,那么用数学表示就是a(4)=a(3)+2=(a(2)+2)+2=((a(1)+2)+2)+2

其实递归方法最接近自然，也是最好思考孝行的一个方法，难点就是把对象建模成递归形式，但是好多问题本身就是以递归形式出现的。

普通递归就是数据结构上的堆栈，先进后出。

例如上面x=4,把a(4)放入栈底，然后放入a(3),然后a(2),a(1),a(1)的值已知，出栈，a(1)=2,a(2)出栈a(2)=a(1)+2=2+2=4,a(3)出栈a(3)=a(2)+2=(a(1)+2)+2=6,a(4)出栈a(4)=a(3)+2=(a(2)+2)+2=((a(1)+2)+2)+2=8

再比如楼上的阶乘例子，当n=0 或 1时,0!=1,1!=1,这个是阶乘的初始值，也是递归的终止条件。然后我们知道n!=n*(n-1)!,当n>1时,这样我们又有了递归形式，又可以以递归算法设计程序了。（楼上已给出谭老的程序，我就不写了）。

我给出一种优化的递归算法---尾递归。

从我给出的第一算法可以看出，先进栈再出栈，递归的效率是很低的。速度上完全比不上迭代（循环）。但是尾递归引入了一个新的函数参数，用这个新的函数参数来记录中间值.

普通递归阶乘fac(x),就1个x而已，尾递归用2个参数fac(x,y),y存放阶乘值。

所以谭老的程序就变成

// zysable's tail recursive algorithm of factorial.

int fac(int x, int y) {

if (x == 1)

return y

else return fac(x-1, y*x)}

int ff(int x) {

if (x == 0)

return 1

else return fac(x,1)}

对于这个程序我们先看函数ff，函数ff其实是对fac的一个封装函数，纯粹是为了输入方便设计的，通过调用ff(x)来调用fac(x,1),这里常数1就是当x=1的时候阶乘值了，我通过走一遍当x=3时的值即为3!来说明一下。

首先ff(3),x!=0,执行fac(3,1).第一次调用fac，x=3,y=1,x!=1,调用fac(x-1,y*x),新的x=2,y=3*1=3,这里可以看到，y已经累计了一次阶乘值了，然后x还是!=1,继续第三次调用fac(x-1,y*x),新的x=1,y=2*3=6,然后x=1了，返回y的值是6，也就是3！.你会发现这个递归更类似于迭代了。事实上我们用了y记录了普通递归时候，出栈的乘积，所以减少了出栈后的步骤，而且现在世界上很多程序员都在倡议用尾递归取消循环，因为有些在很多解释器上尾递归比迭代稍微效率一点.

基本所有普通递归的问题都可以用尾递归来解决。

一个问题以递归来解决重要的是你能抽象出问题的递归公式，只要递归公式有了，你就可以放心大胆的在程序中使用，另外一个重点就是递归的终止条件；

其实这个终止条件也是包含在递归公式里面的，就是初始值的定义。英文叫define initial value. 用普通递归的时候不要刻意让自己去人工追踪程序，查看运行过程，有些时候你会发现你越看越不明白，只要递归公式转化成程序语言正确了，结果必然是正确的。学递归的初学者总是想用追踪程序运行来让自己来了解递归，结果越弄越糊涂。

如果想很清楚的了解递归，有种计算机语言叫scheme,完全递归的语言，因为没有循环语句和赋值语句。但是国内人知道的很少，大部分知道是的lisp。

好了，就给你说到这里了，希望你能学好递归。

PS:递归不要滥用，否则程序极其无效率，要用也用尾递归。by 一名在美国的中国程序员zysable。

---