递归的受理方法和技巧

A. 什么是递归函数 怎样实现递归

递归就是一个函数在它的函数体内调用它自身。执行递归函数将反复调用其自身，每调用一次就进入新的一层。递归函数必须有结束条件。

当函数在一直递推，直到遇到墙后返回，这个墙就是结束条件。

所以递归要有两个要素，结束条件与递推关系。

递归有两个基本要素：

（1）边界条件：确定递归到何时终止，也称为递归出口。

（2）递归模式：大问题是如何分解为小问题的，也称为递归体。递归函数只有具备了这两个要素，才能在有限次计算后得出结果

在递归函数中，调用函数和被调用函数是同一个函数，需要注意的是递归函数的调用层次，如果把调用递归函数的主函数称为第0层，进入函数后，首次递归调用自身称为第1层调用；从第i层递归调用自身称为第i+1层。反之，退出第i+1层调用应该返回第i层。

一个递归函数的调用过程类似于多个函数的嵌套的调用，只不过调用函数和被调用函数是同一个函数。为了保证递归函数的正确执行，系统需设立一个工作栈。具体地说，递归调用的内部执行过程如下：

（1）运动开始时，首先为递归调用建立一个工作栈，其结构包括值参、局部变量和返回地址；

（2）每次执行递归调用之前，把递归函数的值参和局部变量的当前值以及调用后的返回地址压栈；

（3）每次递归调用结束后，将栈顶元

(1)递归的受理方法和技巧扩展阅读：

递归就是某个函数直接或间接地调用了自身，这种调用方式叫做递归调用。说白了，还是函数调用。既然是函数调用，那么就有一个雷打不动的原则：所有被调用的函数都将创建一个副本，各自为调用者服务，而不受其他函数的影响。

你的ff函数，递归多少次，就有多少个副本，再利用内存的栈式管理，反向退出。这个最好找一下“栈”这方面的东西看看，挺容易的，就像子弹匣一样，先进后出。

从某种意义上说，这是不对的，因为就像刚才说的，一旦被调用，他将在内存中复制出一份代码，再被调用就再复制一份，换句话说，你可以吧同一个函数的多次调用理解称谓多个不同函数的一次调用，这样也会会简单些。

再说=1和=0是为什么退出。递归，很需要注意的就是死递归，也就是说，某一个函数进入了无限调用自身的情况，永无止境地消耗内存等资源，这在编程方面是一大忌。

但凡是递归的函数，一定会在某一个地方存在能够返回上一层函数的代码，否则必定死递归。ff函数中，那个else就是返回的出口，你可以这样想，如果没有那个if来进行判断，你递归到什么时候算完？ff是不是会一直调用自己。

因为一旦某个函数A中调用了函数B（或者自己），那么A中的代码会停在调用的位置，而转向B中去执行，同理，如果B又调用函数C，那么B又停在调用的位置，去执行C，如果无限调用，那么程序是永远不会结束的。

当然，也有这种情况，A调用B，然后继续自己的代码，不管B的死活，这种不在我们的讨论范围内，因为那牵扯到另一种编程方式：多线程。

B. 递归方法的定义

1、定义是递归的：

（1）n!的递归实现：

递归方法：

public class Method { int fun(int n){ if(n==1) return 1; else
return(fun(n-1)*n);
}
}
public class RecursionDemo { public static void main (String[] args){
Method m=new Method(); int num=m.fun(3);
System.out.println(num);
}
}

递归方法分析：

（1）该方法是直接递归，即自己调用自己。

例如：在执行fun(3)的时候，先执行fun（2）*3，而fun（2）=fun（1）*2，fun（1）=1。

（2）递归过程将问题的规模逐步缩小，参数的大小每次减1。一个个重复的过程，通过调用自身，减少了代码量。

（3）因为递归调用语句是在最后一句，因此，这种递归方式也称为尾递归。

2、数据结构是递归的：

单链表的存储结构定义。

3、问题的求解是递归的：

#include<stdio.h> #include<malloc.h> #include<stdlib.h>#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10#define OVERFLOW -2#define ERROR 0
#define OK 1typedef int ElemType;

typedef struct{ //存储结构 ElemType *elem; //指针类型 int length;
int listsize;
}SqList;//顺序表的结构类型 typedef int Status;

Status InitList(SqList &L){
L.elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));//动态分配存储空间 if(!L.elem) exit(OVERFLOW); //分配失败退出 L.length=0; //空表 L.listsize=LIST_INIT_SIZE; //初始存储容量 return OK;
}

Status ListInsert(SqList &L,int i,ElemType e){//在第 i 个元素前插入一个新的元素e if(i<1 || i > L.length+1) return ERROR; //i值不合法 if(L.length>=L.listsize) //存储空间不足 {
ElemType * newbase=(ElemType *)realloc(L.elem,(LIST_INIT_SIZE+LISTINCREMENT)*sizeof(ElemType));
if(!newbase) exit(OVERFLOW); //分配失败 L.elem=newbase;
L.listsize=LIST_INIT_SIZE+LISTINCREMENT;
}
for (int j=L.length; j>=i; --j)
L.elem[j]=L.elem[j-1];
L.elem[i-1]=e;
L.length++;return OK;
}

Status ListEmpty(SqList L){ //判断顺序表是否为空return L.length == 0;
}

Status ListPrint(SqList &L) {
printf(" 顺序表为： ");
if (ListEmpty(L)) {
printf(" 空。 ");
return ERROR;
}
for (int i=0; i<L.length; ++i)
{
printf("%-4d ", L.elem[i]);
}
printf(" ");
return OK;
}int Sum(SqList L,int i){ if(i==L.length) return 0; else
return(L.elem[i]+Sum(L,i+1));
}

main(){

SqList L;
ElemType e;
int i,j;
InitList(L);


printf(" 请输入你想创建的顺序表中元素的个数： ");
scanf("%d",&i);
if(i<1) printf(" 您输入的值有误，无法创建顺序表。 ");
else {
printf(" 请您依次输入您想创建的顺序表的元素： ");
for(j=1;j<=i;j++)
{
scanf("%d",&e);
ListInsert(L,L.length+1,e); //尾插 }
}
ListPrint(L); //遍历顺序表 int result=Sum(L,0);
printf( "顺序表所有元素的和为：%d",result);
}

这个程序是求解顺序表的元素的和，从顺序表的第一个元素开始，依次向后查找元素，并进行求和运算。

C. 谁能给讲一下递归

递归是一种重要的编程技术。该方法用于让一个函数从其内部调用其自身。一个示例就是计算阶乘。0 的阶乘被特别地定义为 1。 更大数的阶乘是通过计算 1 * 2 * ...来求得的，每次增加 1，直至达到要计算其阶乘的那个数。

下面的段落是用文字定义的计算阶乘的一个函数。

“如果这个数小于零，则拒绝接收。如果不是一个整数，则将其向下舍入为相邻的整数。如果这个数为 0，则其阶乘为 1。如果这个数大于 0，则将其与相邻较小的数的阶乘相乘。”

要计算任何大于 0 的数的阶乘，至少需要计算一个其他数的阶乘。用来实现这个功能的函数就是已经位于其中的函数；该函数在执行当前的这个数之前，必须调用它本身来计算相邻的较小数的阶乘。这就是一个递归示例。

递归和迭代（循环）是密切相关的 — 能用递归处理的算法也都可以采用迭代，反之亦然。确定的算法通常可以用几种方法实现，您只需选择最自然贴切的方法，或者您觉得用起来最轻松的一种即可。

显然，这样有可能会出现问题。可以很容易地创建一个递归函数，但该函数不能得到一个确定的结果，并且不能达到一个终点。这样的递归将导致计算机执行一个“无限”循环。下面就是一个示例：在计算阶乘的文字描述中遗漏了第一条规则（对负数的处理） ，并试图计算任何负数的阶乘。这将导致失败，因为按顺序计算 -24 的阶乘时，首先不得不计算 -25 的阶乘；然而这样又不得不计算 -26 的阶乘；如此继续。很明显，这样永远也不会到达一个终止点。

因此在设计递归函数时应特别仔细。如果怀疑其中存在着无限递归的可能，则可以让该函数记录它调用自身的次数。如果该函数调用自身的次数太多，即使您已决定了它应调用多少次，就自动退出。

下面仍然是阶乘函数，这次是用 JScript 代码编写的。

// 计算阶乘的函数。如果传递了
// 无效的数值（例如小于零），
// 将返回 -1，表明发生了错误。若数值有效，
// 把数值转换为最相近的整数，并
// 返回阶乘。
function factorial(aNumber) {
aNumber = Math.floor(aNumber); // 如果这个数不是一个整数，则向下舍入。
if (aNumber < 0) { // 如果这个数小于 0，拒绝接收。
return -1;
}
if (aNumber == 0) { // 如果为 0，则其阶乘为 1。
return 1;
}
else return (aNumber * factorial(aNumber - 1)); // 否则，递归直至完成。
}

D. 讲一下c语言中递归函数的使用方法

递归函数有三点要求：

1，递归的终止点，即递归函数的出口

2，不断的递归调用自身

3，递归函数主体内容，即递归函数需要做的事情

ps：3一般可以放在2的前面或者后面，一般1放最前面。另外，2和3可以根据不同的需要合并，比如，有时候递归函数的主体就是返回调用下层函数所得到的结果。

具体例子如下：

voidfun(intn)
{
if(n<=0)return;//1这是递归的终点，即出口
fun(n-1);//2、递归函数自身的调用
cout<<n<<endl;//3递归函数的主体内容
}

2,3合并的情况

intfun(intn)
{
if(n<=0)return0;
returnfun(n-1)+fun(n-2);//23合并
}

E. 递归的原理解释

递归的原理解释：
递归，是函数实现的一个很重要的环节，很多程序中都或多或少的使用了递归函数。递归的意思就是函数自己调用自己本身，或者在自己函数调用的下级函数中调用自己。
递归之所以能实现，是因为函数的每个执行过程都在栈中有自己的形参和局部变量的拷贝，这些拷贝和函数的其他执行过程毫不相干。这种机制是当代大多数程序设计语言实现子程序结构的基础，是使得递归成为可能。假定某个调用函数调用了一个被调用函数，再假定被调用函数又反过来调用了调用函数。这第二个调用就被称为调用函数的递归，因为它发生在调用函数的当前执行过程运行完毕之前。而且，因为这个原先的调用函数、现在的被调用函数在栈中较低的位置有它独立的一组参数和自变量，原先的参数和变量将不受影响，所以递归能正常工作。程序遍历执行这些函数的过程就被称为递归下降。
程序员需保证递归函数不会随意改变静态变量和全局变量的值，以避免在递归下降过程中的上层函数出错。程序员还必须确保有一个终止条件来结束递归下降过程，并且返回到顶层。

F. 递归主方法

递归的主要方法是什么？

一、递归算法
递归算法（英语：recursion algorithm）在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法。递归式方法可以被用于解决很多的计算机科学问题，因此它是计算机科学中十分重要的一个概念。绝大多数编程语言支持函数的自调用，在这些语言中函数可以通过调用自身来进行递归。计算理论可以证明递归的作用可以完全取代循环，因此在很多函数编程语言（如Scheme）中习惯用递归来实现循环。
二、递归程序
在支持自调的编程语言中，递归可以通过简单的函数调用来完成，如计算阶乘的程序在数学上可以定义为：

这一程序在Scheme语言中可以写作：
1
(define (factorial n) (if (= n 0) 1 (* n (factorial (- n 1)))))
不动点组合子
即使一个编程语言不支持自调用，如果在这语言中函数是第一类对象（即可以在运行期创建并作为变量处理），递归可以通过不动点组合子（英语：Fixed-point combinator）来产生。以下Scheme程序没有用到自调用，但是利用了一个叫做Z 算子（英语：Z combinator）的不动点组合子，因此同样能达到递归的目的。
1
(define Z (lambda (f) ((lambda (recur) (f (lambda arg (apply (recur recur) arg)))) (lambda (recur) (f (lambda arg (apply (recur recur) arg)))))))(define fact (Z (lambda (f) (lambda (n) (if (<= n 0) 1 (* n (f (- n 1))))))))
这一程序思路是，既然在这里函数不能调用其自身，我们可以用 Z 组合子应用(application)这个函数后得到的函数再应用需计算的参数。
尾部递归
尾部递归是指递归函数在调用自身后直接传回其值，而不对其再加运算。尾部递归与循环是等价的，而且在一些语言（如Scheme中）可以被优化为循环指令。 因此，在这些语言中尾部递归不会占用调用堆栈空间。以下Scheme程序同样计算一个数字的阶乘，但是使用尾部递归：
1
(define (factorial n) (define (iter proct counter) (if (> counter n) proct (iter (* counter proct) (+ counter 1)))) (iter 1 1))
三、能够解决的问题
数据的定义是按递归定义的。如Fibonacci函数。
问题解法按递归算法实现。如Hanoi问题。
数据的结构形式是按递归定义的。如二叉树、广义表等。
四、递归数据
数据类型可以通过递归来进行定义，比如一个简单的递归定义为自然数的定义：“一个自然数或等于0，或等于另一个自然数加上1”。Haskell中可以定义链表为：
1
data ListOfStrings = EmptyList | Cons String ListOfStrings
这一定义相当于宣告“一个链表或是空串行，或是一个链表之前加上一个字符串”。可以看出所有链表都可以通过这一递归定义来达到。

G. 请教高人 递归算法编写思路技巧

一个子程序（过程或函数）的定义中又直接或间接地调用该子程序本身，称为递归。递归是一种非常有用的程序设计方法。用递归算法编写的程序结构清晰，具有很好的可读性。递归算法的基本思想是：把规模大的、较难解决的问题变成规模较小的、易解决的同一问题。规模较小的问题又变成规模更小的问题，并且小到一定程度可以直接得出它的解，从而得到原来问题的解。
利用递归算法解题，首先要对问题的以下三个方面进行分析：
一、决定问题规模的参数。需要用递归算法解决的问题，其规模通常都是比较大的，在问题中决定规模大小（或问题复杂程度）的量有哪些？把它们找出来。
二、问题的边界条件及边界值。在什么情况下可以直接得出问题的解？这就是问题的边界条件及边界值。
三、解决问题的通式。把规模大的、较难解决的问题变成规模较小、易解决的同一问题，需要通过哪些步骤或等式来实现？这是解决递归问题的难点。把这些步骤或等式确定下来。
把以上三个方面分析好之后，就可以在子程序中定义递归调用。其一般格式为：
if 边界条件 1 成立 then
赋予边界值 1
【 elseif 边界条件 2 成立 then
赋予边界值 2
┇ 】
else
调用解决问题的通式
endif
例 1 ： 计算勒让德多项式的值

x 、 n 由键盘输入。
分析： 当 n ＝ 0 或 n ＝ 1 时，多项式的值都可以直接求出来，只是当 n ＞ 1 时，才使问题变得复杂，决定问题复杂程度的参数是 n 。根据题目提供的已知条件，我们也很容易发现，问题的边界条件及边界值有两个，分别是：当 n ＝ 0 时 P n (x) ＝ 1 和当 n ＝ 1 时 P n (x) ＝ x 。解决问题的通式是：
P n (x) ＝ ((2n － 1)P n － 1 (x) － (n － 1)P n － 2 (x)) ／ n 。
接下来按照上面介绍的一般格式定义递归子程序。
function Pnx(n as integer)
if n ＝ 0 then
Pnx ＝ 1
elseif n ＝ 1 then
Pnx ＝ x
else
Pnx ＝ ((2*n － 1)*Pnx(n － 1) － (n － 1)*Pnx(n － 2)) ／ n
endif
end function
例 2 ： Hanoi 塔问题：传说印度教的主神梵天创造世界时，在印度北部佛教圣地贝拿勒斯圣庙里，安放了一块黄铜板，板上插着三根宝石针，在其中一根宝石针上，自下而上地放着由大到小的 64 个金盘。这就是所谓的梵塔（ Hanoi ），如图。梵天要求僧侣们坚持不渝地按下面的规则把 64 个盘子移到另一根针上：

(1) 一次只能移一个盘子；
(2) 盘子只许在三根针上存放；
(3) 永远不许大盘压小盘。
梵天宣称，当把他创造世界之时所安放的 64 个盘子全部移到另一根针上时，世界将在一声霹雳声中毁灭。那时，他的虔诚的信徒都可以升天。
要求设计一个程序输出盘子的移动过程。
分析： 为了使问题更具有普遍性，设共有 n 个金盘，并且将金盘由小到大依次编号为 1 ， 2 ，…， n 。要把放在 s(source) 针上的 n 个金盘移到目的针 o(objective) 上，当只有一个金盘，即 n ＝ 1 时，问题是比较简单的，只要将编号为 1 的金盘从 s 针上直接移至 o 针上即可。可定义过程 move(s,1,o) 来实现。只是当 n>1 时，才使问题变得复杂。决定问题规模的参数是金盘的个数 n ；问题的边界条件及边界值是：当 n ＝ 1 时， move(s,1,o) 。
当金盘不止一个时，可以把最上面的 n － 1 个金盘看作一个整体。这样 n 个金盘就分成了两个部分：上面 n － 1 个金盘和最下面的编号为 n 的金盘。移动金盘的问题就可以分成下面三个子问题（三个步骤）：
(1) 借助 o 针，将 n － 1 个金盘（依照上述法则）从 s 针移至 i(indirect) 针上；
(2) 将编号为 n 的金盘直接从 s 针移至 o 针上；
(3) 借助 s 针，将 i 针上的 n － 1 个金盘（依照上述法则）移至 o 针上。如图

其中第二步只移动一个金盘，很容易解决。第一、第三步虽然不能直接解决，但我们已经把移动 n 个金盘的问题变成了移动 n － 1 个金盘的问题，问题的规模变小了。如果再把第一、第三步分别分成类似的三个子问题，移动 n － 1 个金盘的问题还可以变成移动 n － 2 个金盘的问题，同样可变成移动 n － 3 ，…， 1 个金盘的问题，从而将整个问题加以解决。
这三个步骤就是解决问题的通式，可以以过程的形式把它们定义下来：
hanoi(n － 1,s,o,i)
move(s,n,o)
hanoi(n － 1,i,s,o)
参考程序如下：
declare sub hanoi(n,s,i,o)
declare sub move(s,n,o)
input "How many disks?",n
s ＝ 1
i ＝ 2
o ＝ 3
call hanoi(n,s,i,o)
end
sub hanoi(n,s,i,o)
rem 递归子程序
if n ＝ 1 then
call move(s,1,o)
else
call hanoi(n － 1,s,o,i)
call move(s,n,o)
call hanoi(n － 1,i,s,o)
endif
end sub
sub move(s,n,o)
print "move disk";n;
print "from";s;"to";o
end sub

H. 关于递归

1、调用子程序的含义：
在过程和函数的学习中，我们知道调用子程序的一般形式是：主程序调用子程序A，子程序A调用子程序B，如图如示，这个过程实际上是：

＠当主程序执行到调用子程序A语句时，系统保存一些必要的现场数据，然后执行类似于BASIC语言的GOTO语句，跳转到子程序A（为了说得简单些，我这里忽略了参数传递这个过程）。
＠当子程序A执行到调用子程序B语句时，系统作法如上，跳转到子程序B。
＠子程序B执行完所有语句后，跳转回子程序A调用子程序B语句的下一条语句（我这又忽略了返回值处理）
＠子程序A执行完后，跳转回主程序调用子程序A语句的下一条语句
＠主程序执行到结束。
做个比较：我在吃饭（执行主程序）吃到一半时，某人叫我（执行子程序A），话正说到一半，电话又响了起来（执行子程序B），我只要先接完电话，再和某人把话说完，最后把饭吃完（我这饭吃得也够累的了J）。
2、认识递归函数
我们在高中时都学过数学归纳法，例：
求 n！
我们可以把n！这么定义

也就是说要求3！，我们必须先求出2！，要求2！，必须先求1！，要求1！，就必须先求0！，而0!=1，所以1!=0!*1=1，再进而求2!，3!。分别用函数表示，则如图：

我们可以观察到，除计算0！子程序外，其他的子程序基本相似，我们可以设计这么一个子程序：
int factorial(int i){
int res;
res=factorial(I-1)*i;
return res;
}
那么当执行主程序语句s=factorial(3)时，就会执行factorial(3),但在执行factorial(3)，又会调用factorial(2)，这时大家要注意，factorial(3)和factorial(2)虽然是同一个代码段，但在内存中它的数据区是两份！而执行factorial(2)时又会调用factorial（1），执行factorial（1）时又会调用factorial（0），每调用一次factorial函数，它就会在内存中新增一个数据区，那么这些复制了多份的函数大家可以把它看成是多个不同名的函数来理解；
但我们这个函数有点问题，在执行factorial（0）时，它又会调用factorial（－1）。。。造成死循环，也就是说，在factorial函数中，我们要在适当的时候保证不再调用该函数，也就是不执行res=factorial(I-1)*i;这条调用语句。所以函数要改成：
int factorial(int i){
int res;
if (I>0) res=factorial(I-1)*i; else res=1;
return res;
}
那么求3!的实际执行过程如图所示：

3、如何考虑用递归的方法来解决问题
例：求s=1+2+3+4+5+6+……+n
本来这个问题我们过去常用循环累加的方法。而这里如要用递归的方法，必须考虑两点：
1） 能否把问题转化成递归形式的描述；
2） 是否有递归结束的边界条件。
设:函数s(n)=1+2+3+…+(n-1)+n
显然递归的两个条件都有了：
1） s(n) =s(n-1)+n
2） s(1)=1
所以源程序为：
int progression(int n){
int res;
if (n=1 )res=1 else res=progression(n-1)+n;
return res;
}
4、递归的应用
中序遍历二叉树
void inorder (BinTree T){
if (T){
inorder(T->lchild);
printf(“%c”,T->data);
inorder(T->rchild);
}
}
现假设树如图（为了讲解方便，树很简单）

＠执行第一次调用inorder1，T指向顶结点，T不为空，所以第二次调用inorder2；
＠T指向顶结点的左子树结点也就是B，不为空，所以第三次调用inorder3；
＠T指向B结点的左子树结点，为空，所以什么都不执行，返回inorder2；
＠打印B结点的DATA域值“b”；
＠第四次调用inorder4，去访问B子树的右结点
＠T指向B结点的右子树结点，为空，所以什么都不执行，返回inorder2；
＠返回inorder1；
＠打印A结点的DATA域值“a”；
＠第五次调用inorder5，去访问A子树的右结点；
＠T指向A结点的右子树结点，为空，所以什么都不执行，返回inorder1；
＠inorder1执行完毕，返回。

I. 解递归方程的三个方法

1、主方法求解递归式

一种求解大部分递归式的公式。给出递归式: T(n) = a * T(n/b) + f(n) ，其中a>=1，b>1，f(n)是给定的函数，T(n)是定义在非负整数上的递归式。

2、递归树求解

用主方法求解不了的递归式，我们可以用递归树来猜测解的上界，然后用代入法来证明解的正确性。递归树的求解精确度取决于画递归树的精确度。

3、代入法

比如我们求解，递归式T(n) = 2T(n/2)+n，我们猜测解是O(nlgn)，我们要寻找到一个常数c，使得T(n)<=cnlgn。

即T(n) <= 2c(n/2)lg(n/2)+n <= cnlgn-cnlg2+n = cnlgn-cn+n

只要c>=1，T(n)<=cnlgn，所以我们的猜测是正确的。

要注意的是，代入法全凭经验，通常用递归树来确定上界，然后用代入法再证明。

(9)递归的受理方法和技巧扩展阅读：

设p0，p1，…，pn，…是一个序列。如果pn和序列中在它前面的若干项联系起来的一个关系式对所有大于等于某个整数n0的整数n都是有效的，则称这个关系式为递归关系(recursive relation)式。

如：设(a0，a1，...，ar，...)是一个序列，把该序列中的ar和它前面的几个ai(0≤i<r)关联起来的方程称做一个递归关系。如关系式:ar=3ar-1(r≥1)和错排数:Dn=(n-1)(Dn-1+Dn-2) (n=3，4，...)，都是递归关系。

J. 什么情况下可以利用递归来解决问题再写递归程序时应注意是什么

比如阶乘，也就是说求n可以先求n-1，以此类推，到1，这类问题都可以用递归解决，菲波拉锲数也可以递归。因为递归是总是调用自身解决问题，所以，必须有结束条件，否则会出问题，导致内存卡爆