递归算法做题思路

Ⅰ (1-2+3-4+5-6+7-8+9)用递归方法怎么写

首先要理解递归本身其实是一项非常重要的算法技巧。
递归满足两个条件：
1，不断调用函数本身，也就是递归函数。
2，调用是有限的，也就是递归出口。
为了理解方便，下面是用一个最简单的例子：求n的阶乘。
n!(阶乘)定义：
n!数学意思为n!
=
n*(n-1)!
&
1!=1;
其实根据上面递归定义结合分析下就可以n阶乘的递归算法：
1,构造一个递归函数,不断乘以自身和使用自身减一后调用同样函数．
2,定义出口，当函数参数等于1时结束;
如果用iso
c++语言描述如下：
int
factorial(int
n){
if(
n
>
1){
return
n*factorial(n-1);//递归函数调用
}
else
if(n
==
1){
return
1;
//递归出口
}
else{
return
error;//报告输入错误
}
}
这里讨论主要的不是上面这个简单的例子，而是下面的一些改良．
因为递归设计大量的堆栈操作，所以一般都会考虑将递归转为非递归来执行．
这里用上面这个程序作一个分析例子来分析．
假设这里执行factorial(4)，那么程序会按照下面方式来执行：
(1)执行factorial(4)判断n
>
1执行factorial(3),并且将factorial(4)函数相关信息存入一个堆栈．
(2)执行factorial(3)判断n
>
1执行factorial(2),并且将factorial(3)函数相关信息存入一个堆栈．
(3)执行factorial(2)判断n
>
1执行factorial(1),并且将factorial(2)函数相关信息存入一个堆栈．
(4)执行factorial(1)判断n
==
1执行返回1;
(5)将factorial(2)函数从堆栈中弹出，执行2*1，并且返回2．
(6)将factorial(3)函数从堆栈中弹出，执行2*3，并且返回6．
(7)将factorial(4)函数从堆栈中弹出，执行6*4，并且返回24．
如下图所示：
factorial(4)
-->factorial(3);
-->factorial(2);
-->factorail(1);
<--factorail(1);
<--factorial(2);
<--factorial(3);
<--结果
可以看到中间涉及的堆栈操作是很大的开销，每次需要保存当前函数的所有信息．
为了避免这样情况，可以使用下面这几种方法来实现递归到非递归的转换．
(1)
循环方法
循环方法是所有递归到非递归的转换中最理想的方法，可以将开销减少到最小．
不过也是分析起来最复杂的，对于简单的递归可以用这样的方法来处理．
例如：factorial计算
这里回到n!(阶乘)定义上面来分析，这里将n!数学意思为n!
=
n*(n-1)!
&
1!=1;做一个扩展可以到到n!另外一个表示方法n!
=
n*(n-1)*(n-2)*....*1;
这样就可以很容易得到另外一个定义：
n!表示执行n次循环计算一个增量k，初始k=1和结果t=1;每次t乘以k++的值.
iso
c++实现代码如下：
factorial(int
n){
int
k
=
1
;//增量
int
t
=
1
;//临时结果
while(k!=n){
t*=k;
k++;
}
return
t;
}
这样可以避免递归带来的大量堆栈操作．
(2)
自定义堆栈
对于复杂逻辑的堆栈操作，需要借助外部堆栈来实现．
因为对于所有的递归操作最后分析出来都是形成的一颗树形结构．
下面是一个递归实现factorial的一个方法，虽然在这个程序中对比循环来相对复杂，不过对于一些不能分析出来循环的递归操作来说自定义堆栈的方法可以达到空间开销可控．
factorial(int
n){
stack
s;
int
t
=
1;//临时变量
s.push(n);
while(s.top()!=1)[
t
*=
s.top();
s.push(s.top()-1);
s.pop();
}
return
t;
}
除了上面这两种方法外，还可以使用一种迭代的方法实现递归到非递归的处理．

Ⅱ 递归主方法

递归的主要方法是什么？

一、递归算法
递归算法（英语：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
这一定义相当于宣告“一个链表或是空串行，或是一个链表之前加上一个字符串”。可以看出所有链表都可以通过这一递归定义来达到。

Ⅲ 简述递归问题的求解过程

递归算法的执行过程分递推和回归两个阶段。在递推阶段，把较复杂的问题（规模为n）的求解推到比原问题简单一些的问题（规模小于n）的求解。例如上例中，求解fib(n)，把它推到求解fib(n-1)和fib(n-2)。也就是说，为计算fib(n)，必须先计算fib(n-1)和fib(n-2)，而计算fib(n-1)和fib(n-2)，又必须先计算fib(n-3)和fib(n-4)。依次类推，直至计算fib(1)和fib(0)，分别能立即得到结果1和0。在递推阶段，必须要有终止递归的情况。例如在函数fib中，当n为1和0的情况。
在回归阶段，当获得最简单情况的解后，逐级返回，依次得到稍复杂问题的解，例如得到fib(1)和fib(0)后，返回得到fib(2)的结果，……，在得到了fib(n-1)和fib(n-2)的结果后，返回得到fib(n)的结果。
在编写递归函数时要注意，函数中的局部变量和参数只是局限于当前调用层，当递推进入“简单问题”层时，原来层次上的参数和局部变量便被隐蔽起来。在一系列“简单问题”层，它们各有自己的参数和局部变量。

Ⅳ java中递归算法是什么怎么算的

一、递归算法基本思路：

Java递归算法是基于Java语言实现的递归算法。递归算法是一种直接或者间接调用自身函数或者方法的算法。递归算法实质是把问题分解成规模缩小的同类问题的子问题，然后递归调用方法表示问题的解。递归往往能给我们带来非常简洁非常直观的代码形式，从而使我们的编码大大简化，然而递归的思维确实跟我们的常规思维相逆的，通常都是从上而下的思维问题，而递归趋势从下往上的进行思维。

二、递归算法解决问题的特点：

【1】递归就是方法里调用自身。

【2】在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。

【3】递归算法代码显得很简洁，但递归算法解题的运行效率较低。所以不提倡用递归设计程序。

【4】在递归调用的过程中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等，所以一般不提倡用递归算法设计程序。

【5】在做递归算法的时候，一定把握出口，也就是做递归算法必须要有一个明确的递归结束条件。这一点是非常重要的。其实这个出口就是一个条件，当满足了这个条件的时候我们就不再递归了。

三、代码示例：

publicclassFactorial{

//thisisarecursivefunction

intfact(intn){

if(n==1)return1;

returnfact(n-1)*n;

}}

publicclassTestFactorial{publicstaticvoidmain(String[]args){

//TODOAuto-generatedmethodstub

Factorialfactorial=newFactorial();

System.out.println("factorial(5)="+factorial.fact(5));

}
}

代码执行流程图如下：

此程序中n=5就是程序的出口。

Ⅳ 汉诺塔递归算法是什么

hanot (n-1,b,a,c);（解释：在把B塔上的(n-1))个借助A塔移动到C塔）

为了实现 n个盘从 借助c 从a 移动到 b

思路如下：

首先考虑极限当只有一个盘的时候，盘直接从 a -> b即可。

当有2个盘的时候，把1号盘从a -> c 然后 把2号盘 a->b 再 把 2好盘从 c - > b。

当有n个盘的时候，把 n-1个 盘 借助 b 移动到 c 然后将 n号盘从 a -> b。

这时候只要将 n-1想办法从c移动到 b 借助 a 那么就可以先把 n-2个盘借助b移动到a。

递归，就是在运行的过程中调用自己。

构成递归需具备的条件：

1，子问题须与原始问题为同样的事，且更为简单；

2，不能无限制地调用本身，须有个出口，化简为非递归状况处理。

在数学和计算机科学中，递归指由一种（或多种）简单的基本情况定义的一类对象或方法，并规定其他所有情况都能被还原为其基本情况。

以上内容参考：网络-递归公式