如何建立递归的思想 _递归函数的基本思想

递归就是某个函数直接或间接调用自身的问题求解过程，通过将自身问题划分成相同性质的子问题的求解过程。
培养：
1、找出递推关系式；
2、找到递归终止条件。
要点：
1、将原问题划分成子问题；
2、递归终止的条件，最小子问题的求解，允许有多个出口；
3、界函数，它保证递归的规模向出口靠拢。
如何建立递归的思想很多初学者往往对递归迷惑不解，也在这上面花了不少的时间。其实教材上的例子很经典，只是它说的有一些唠叨了。初学者会看的头大的。编程是解决问题的，而现实中很多的问题都是比较简单的，没有象汉诺塔那么复杂。我们也不必追究递归到底是怎样实现的，我们只是要会用递归，会用递归来为我们解决一些问题，这就行了。
首先来看一个例子：
有一个Febonacci序列：
1,1,2,3,5,8,13,,21,34........
它的问题是：求这个序列中的第N个数。
由于它的函数原形是：f(n)=f(n-1)+f(n-2)
这用递归很容易就可以写出代码来，一点都不费事：
int Febc(int n) {
if(n<3) return (1)
else
return (Febc(n-1)+Febc(n-2))
}
噢~~~~~也许你会说递归真是太简单了，简直就是一个数学模型嘛，呵呵。
其实，递归函数的工作过程就是自己调用自己。有一些问题用递归就很容易解决，简单的你自己都会吃惊。
我们做事情，一般都是从头开始的，而递归却是从末尾开始的。比如上面的函数吧，当n>3时，它显然只能求助于n-1,n-2 。而(n-1)>2,(n-2)>2时，它们就求助于：(n-1)-1,(n-1)-2(n-2)-1,(n-2)-2然后··············直到（n-k)<3,(n-k-1)<3时，函数Febc终于有了返回值1 了，它再从头开始计算，然后一直算到n 为止。
通过上面的例子，我们知道递归一定要有一个停止的条件，否则递归就不知道停止了。在上面的例子中， if(n<3) return (1) 就是停止的条件。
然而，使用递归的代价是十分巨大的：它会消耗大量的内存！！递归循环时它用的是堆栈，而堆栈的资源是十分有限的。上面的例子你只能用一个很小的n值。如果n=20，即Febc(20)的话，它将调用Febc(n)函数10000多次！！！而上面一个例子用循环也是十分容易写的：
int febc(int)
main()
{
int n
scanf("%d",&n)
febc(n)
}
int febc(int n)
{
int a[3],i
a[0]=a[1]=a[2]=1
for(i=3i<=ni++)
a[i%3]=a[(i+1)%3]+a[(i+2)%3]
printf("n%dn",a[n%3])
}
有兴趣者不妨输入一个较大的n值，然后比较比较这二个函数计算的速度。当然，如果你使用的n太大的话，递归可能发生错误。如果死机了可别骂我哦~~~ 我已经提醒过你了：）
现在我们再来看看一个求从1 加到100的循环：
main()
{ int i,n
for(i=1i<101i++)
n+=i }
这很简单没什么可说的。但是，你能不能写出相应的递归函数呢？
递归函数的基本思想递归函数的基本思想如下：
递归就是方法自己调用自己递归特点: 有临界点当一个方法执行完毕,或者遇到retrun,就会返回,函数就是出栈。
待求解问题的解输入变量x的函数f(x)，通过寻找函数g( ), 使得f(x) = g(f(x-1)) 。
且已知f(0)的值, 就可以通过f(0)和g( )求出f(x)的值。
扩展到多个输入变量x, y, z等, x-1也可以推广到 x - x1 , 只要递归朝着 “出口” 的方向即可。
把一个问题划分成一组子问题, 依次对这些子问题求解。
子问题之间是横向的, 同类的关系递归: 把一个问题逐级分解成子问题。
子问题与原问题之间是纵向的, 同类的关系。
语法形式上: 在一个函数的运行过程中, 调用这个函数自己。
直接调用: 在fun()中直接执行fun() 。
间接调用: 在fun1()中执行fun2() 在fun2()中又执行fun1() 递归与枚举的区别。
递归的三个要点：
递归式：如何将原问题划分成子问题。
递归出口: 递归终止的条件, 即最小子问题的求解,可以允许多个出口。
界函数: 问题规模变化的函数, 它保证递归的规模向出口条件靠拢，求阶乘的递归程序。
请教高人递归算法编写思路技巧一个子程序（过程或函数）的定义中又直接或间接地调用该子程序本身，称为递归。递归是一种非常有用的程序设计方法。用递归算法编写的程序结构清晰，具有很好的可读性。递归算法的基本思想是：把规模大的、较难解决的问题变成规模较小的、易解决的同一问题。规模较小的问题又变成规模更小的问题，并且小到一定程度可以直接得出它的解，从而得到原来问题的解。