用堆栈实现递归其实并没有消除递归,只不过人工做了本来由编译器做的事情。真正的非递归是指运算时所需要的空间是常数,即所需空间与问题的输入规模无关。并非所有递归都可以转换成非递归,比如著名的Ackmann函数。
递归转非递归方法:
(1)用一般公式直接代替。象经常看到的斐波那契数列,它就存在通项公式,而无需采用递归实现。
(2)使用栈来实现
(3)通过Cooper变换、反演变换将一些递归转化为尾递归,从而迭代求出结果
至于什么是Cooper变换,反演变换,这可得好好研究数学。这里贴两个变换实例。
计算阶乘的递归实现(用Haskell实现的,谁都看得懂):f x = if x = 0 then 1 else f(x-1)*x;
第一步:转变成尾递归
int G(int x, int y)
{
int x1, y1;
if (x == 1) {
return 1 * y;
} else {
x1 = x - 1;
y1 = x *y;
return G(x1, y1);
}
}
int f(int x)
{
return G(x, 1);
}
第二步:转变成迭代
int G(int x, int y)
{
int x1, y1;
loop:
if (x == 1) {
return 1 * y;
} else {
x1 = x - 1;
y1 = x *y;
x = x1
y = y1;
goto loop;
}
}
求斐波那契值:
f x |x==0 =0
|x==1 =1
|otherwise = f (x-1)+f (x-2)
第一步:转变成尾递归
int fib(int n){
if(n==0)
return 0;
return _fib(n,1,0);
}
int _fib(int n,int f1,int f2){
if(n==1)
return f1;
return _fib(n-1,f1+f2,f1);
}
第二步:转变成迭代(略)
分享到:
相关推荐
n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---...
基础算法-递归-杨鑫20191010.pptx,基础算法-递归-杨鑫20191010.pptx,基础算法-递归-杨鑫20191010.pptx
编译原理-递归子程序 c++源码 编译原理-递归子程序 c++源码 编译原理-递归子程序 c++源码
算法-基础算法- 递归算法(包含源程序).rar
SPT-05-递归程序设计.pdf
2021-算法设计与分析-02-递归与分治-2.pdf
汉诺塔非递归程序,包含详细的解析、代码、结果及心得
大师叫你不再害怕 ----递归 大师叫你不再害怕 ----递归 大师叫你不再害怕 ----递归
编译原理课程设计---递归下降分析程序的实现
《数据结构与算法》-李春葆 实验报告-递归算法实践-n皇后问题
递归算法的基本思想是将一个大问题分解成若干个小问题,然后递归地解决这些小问题,最终将它们合并成一个解决方案。递归算法通常使用递归函数来实现,递归函数是一种可以调用自身的函数。 递归算法的实现需要注意...
百鸡问题 递归与非递归求最大公约数 斐波那契数列递归与非递归算法 递归与非递归求阶乘
快速选择非递归与递归算法实现
文档中涵盖了递归阶乘的基本概念,包括如何使用递归计算阶乘以及如何在Java中实现递归阶乘。此外,文档还包括一个逐步指南,介绍如何在Java中实现递归阶乘的代码,包括详细的代码示例和实现细节。 文档还涵盖了高级...
非递归的先中後序, 计算出深度 结点数 /* 运行结果: ------------------------ 请先序输入二叉树(如:ab三个空格表示a为根节点,b为左子树的二叉树) ab c 先序递归遍历二叉树: a b c 先序非递归遍历二叉树: a b ...
计算机软件技术基础-递归程序设计.ppt
本ppt讲述了递归的定义与使用技巧,可以帮助程序员对递归程序的阅读理解;还包含递归算法的设计实例;还讲述了递归转非递归的技巧和方法,步骤;最后附有关于递归算法的习题。
/*选择二叉链式存储结构作为二叉树的存储结构,设计一个程序实现二叉树的基本操作(包括建立、输出、前序遍历、中序遍历、后序遍历、求树高、统计叶子总数等) 【实验内容】 必做内容 程序的菜单功能项如下: 1----...
RLS递归最小二乘方自适应算法源程序-rls算法.rar RLS(递归最小二乘方自适应算法源程序)
递归算法转为非递归算法。方法、过程,用栈的原理