递归算法转换成非递归代码

Ⅰ (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;
}
除了上面这两种方法外，还可以使用一种迭代的方法实现递归到非递归的处理．

Ⅱ 在C语言中什么叫递归

递归：就是自己调自己，但是没终止条件会死循环，所以你的递归代码里有结束自调自的条件，这样就创造了有限次的循环（代码中你看不到for或foreach但是有循环发生）

Ⅲ 所有的递归程序都能转化为非递归么

是的，所有递归都可以换成非递归，效率方面不一定能提高，看具体算法。

Ⅳ python汉诺塔非递归

python汉诺塔非递归，运用list和function知识的解答

无论stack还是recursion都是从汉诺塔的原理去解决问题，但如果已经想清楚汉诺塔的原理，其实只用把答案print出来就行了

先找规律：

一层：A-->C

两层：A-->B

-------

A-->C

-------

B-->C

三层：A-->C

A-->B

C-->B

-------

A-->C

-------

B-->A

B-->C

A-->C

注意到n层汉诺塔有(2**n) - 1 个步骤，而中间的一步（两个分割线之间）都是“A-->C”，中间的这一步将这一层汉诺塔的解分为上下两个部分

仔细观察，上面一部分是将上一层的解中所有的B，C交换，下面一部分是将上一层的解中所有的A，B交换

例如第二层是：

A-->B

A-->C

B-->C

第三层上部分就将第二层的解的C换成B，B换成C，即得出：

A-->C

A-->B

C-->B

第三层下部分就将第二层的解的A换成B，B换成A，即得出：

B-->A

A-->C

C-->B

这个规律同样适用于第一层，和以后的所有层

然后就好办了，代码如图：

代码

其中convertAB,convertBC就是AB交换，BC交换的函数，这两个函数可以自己定义，用中间变量即可

Ⅳ python-027-递归-求序列最大值、计算第n个调和数、转换字符到整数

递归，emmmmmmm，拥有一种魅力，接近人的立即思维，容易理解，又不容易理解。

递归算法的优点： 它使我们能够简洁地利用重复结构呈现诸多问题。通过使算法描述以递归的方式利用重复结构，我们经常可以避开复杂的案例分析和嵌套循环。这种算法会得出可读性更强的算法描述，而且十分有效。

但是 ，递归的使用要根据相应的成本来看，每次递归python解释器都会给一个空间来记录函数活动状态。但是有时候内存成本很高，有时候将递归算法转为非递归算法是一种好办法。

当然我们可以换解释器、使用堆栈数据结构等方法，来管理递归的自身嵌套，减小储存的活动信息，来减小内存消耗。

最近算法学到了递归这一块，写了三个课后习题：

给一个序列S，其中包含n个元素，用递归查找其最大值。

输出：

调和数：Hn = 1 + 1/2 + 1/3 + ··· + 1/n

输出：

例如："12345"<class 'str'> 转换为12345<class 'int'>

输出：

递归分为线性递归、二路递归、多路递归。