`

递归转非递归通用模型

 
阅读更多
递归转非递归总结:

递归的时候,计算机透明的帮我们做了入栈,出栈等等操作,而且在入栈的时候,还记录了上下文信息,很重要的是记录了当此节点出栈后,应该继续从什么位置进行执行。
若我们自己进行递归转非递归,那么我们就得自己记录上面的信息了。入栈及记录出栈后从什么位置开始执行。

列子:
递归
public class Recursion {


public static int count = 0;
public static int childrenCount = 5;
public static void builderTree(int[] tree,int index) {
if(tree.length <= index) {
return ;
}
tree[index] = count++;

for (int i = childrenCount*index+1,j=0; j < childrenCount; j++,i++) {

builderTree(tree,i);
}
}


public static void main(String[] args) {

int[] tree = new int[500];
builderTree(tree, 0);

System.out.println(Arrays.toString(tree));

// visitTree(tree, 0);
NoneRecursion.visitTree(tree,childrenCount);
}


public static void visitTree(int[] tree,int index) {

if(tree.length <= index) {
return ;
}
System.out.println(tree[index]);

for (int i = childrenCount*index+1,j=0; j < childrenCount; j++,i++) {

visitTree(tree,i);
}
}
}




非递归:

public static void visitTree(int[] tree,int childrenCount) {

LinkedList<Node<Integer>> nodeList = new LinkedList<>();   //递归转非递归后,需要我们自己维护入栈、出栈了


int length = tree.length;

int index = 0;
int upDate = -1;
while(index < length || nodeList.size() > 0) {            


while(index < length) {

if(! (tree[index] > upDate)) {
System.out.println(tree[index] > upDate);
}
upDate = tree[index];
Node<Integer> node = new Node<Integer>();
node.index = 2;
node.t = index;
nodeList.addLast(node);                    //入栈

index = index*childrenCount + 1;    //进行第一个子节点操作
}

if(nodeList.size() == 0) {
break ;
}

Node<Integer> node = nodeList.getLast();          //获取栈中的元素
index = node.t*childrenCount + node.index;        //计算需要访问的获取元素的哪一个子节点

if(node.index == childrenCount) {                 //若访问的子节点是获取元素的最后一个需要操作的子节点
nodeList.pollLast();           //就让此元素出栈
} else {
node.index++;                             //否则标记位下移,表示下次来访问此节点的子节点时候,是访问此次访问的后一个子节点
}
}
}


public static class Node<T>{

T t;
int index;
}



通用模型
public static void visitTree(Tree tree) {

LinkedList<Node<Integer>> nodeList = new LinkedList<>();   //递归转非递归后,需要我们自己维护入栈、出栈了

Tree h = tree;
while(h != null || nodeList.size() > 0) {                 //


while(h != null) {

visitNode(h);   //访问节点操作

//////////////////////////////////////入栈//////////////////////////////////////////////
Node<Tree> node = new Node<Tree>();
node.index = 2;
node.t = h;
nodeList.addLast(node);                    //入栈
////////////////////////////////////////////////////////////////////////////////////


h = getChildrenOfIndex(h,1);    //获取h的第一个子节点     这里完全可以使用函数钩子来实现
}

if(nodeList.size() == 0) {
break ;
}

Node<Tree> node = nodeList.getLast();               //获取栈中的元素
h = getChildrenOfIndex(node.t,node.index);    //获取h的第一个子节点

if(h == null) {   //若访问的子节点是获取元素的最后一个需要操作的子节点
nodeList.pollLast();           //就让此元素出栈
} else {
node.index++;                            //否则标记位下移,表示下次来访问此节点的子节点时候,是访问此次访问的后一个子节点
}
}
}


public static class Node<T>{

T t;
int index;
}
分享到:
评论

相关推荐

    数据结构中递归转非递归算法分析及模型设计研究.pdf

    这种共性使得许多与数据结构相关的递归算法在转换为非递归算法时,可以采用一些通用模型来实现。 为构建数据结构中递归算法的统一知识体系,本研究分析了常见数据结构的递归本质,即数据结构的递归构成元素。以...

    数据结构中递归转非递归算法分析及模型设计研究 (2011年)

    为了实现递归到非递归的转换,本文提出了一些通用模型。这些模型基于对递归算法的分类,能够适应不同的递归算法。在此基础上,作者通过实例分析证明了所提出模型的可行性和效率。具体来讲,模型设计考虑到了递归算法...

    递归算法设计专题讲座

    虽然递归直观且易于理解,但有时为了提高效率或避免栈溢出,可以考虑转换为迭代(非递归)形式。 总之,递归算法是一种强大的工具,它能够简洁地表达复杂问题的解决方案。然而,使用时需要注意其潜在的性能问题,...

    list转树状结构通用工具类

    本篇将深入探讨如何实现一个非递归的、支持多个顶级节点的通用工具类来完成这一任务。 首先,我们需要理解“list转树状结构”的概念。在这个问题中,我们通常有一个扁平化的数据列表,其中每个元素代表一个节点,...

    实现对java类的递归加载

    Java类加载器的工作遵循“双亲委派模型”,即当一个类加载器接收到加载类的请求时,它会首先将这个任务委托给其父类加载器,只有当父类加载器无法完成加载时,当前类加载器才会尝试自己去加载。 在递归加载的场景中...

    一种新型单层递归神经网络解决非光滑伪凸优化问题.pdf

    本文介绍了一种新的单层递归神经网络模型,专门用于解决非光滑伪凸优化问题。非光滑伪凸优化问题在许多科学与工程领域中都有重要应用,因此,研究此类问题具有很高的价值。传统神经网络在处理这类问题时可能存在不足...

    递归算法的优缺点.docx

    3. **优化困难**:编译器对递归的优化通常不如对循环的优化有效,因此递归算法的性能往往低于等效的非递归算法。 除了递归算法,文件中还提到了其他几种算法和概念: - **分治法**:这是一种解决问题的策略,将大...

    τ2模型的非对角Bethe Ansatz解

    通过非对角线的Bethe Ansatz方法研究了具有周期性边界条件的通用量子τ2-模型(也称为Baxter-Bazhanov-Stroganov(BBS)模型)。 根据具有多项式Q函数的非均匀T-Q关系,给出了具有通用的与位置相关的非均匀性参数的...

    Python-TreeRNNs即递归神经网络的Theano实现

    递归神经网络(Recursive Neural Networks,简称Tree RNNs)是一种深度学习模型,它能够处理树状结构的数据,如自然语言中的句法树。在传统的循环神经网络(RNNs)中,序列数据的处理是线性的,而Tree RNNs则可以...

    一维递归神经网络的定性分析.pdf

    此外,论文还指出,一维递归神经网络的平衡点个数与非线性方程的实根问题密切相关。对于一元四次方程,平衡点的存在性并未有统一的解决策略,但通过分析导函数(一元三次方程)的性质,可以推断出平衡点的数量和性质...

    数据模型资源手册

    - **书籍背景与目的**:本书旨在提供一套适用于所有企业的通用数据模型库。它强调了在系统开发过程中使用通用数据模型的重要性,并采取了一种整体性的方法来指导读者如何构建高效的数据结构。 #### 二、目标受众与...

    数据模型资源手册1英文版

    本书旨在提供一系列通用的数据模型框架,帮助开发者快速理解和应用这些模型,以解决实际问题。 #### 三、哪些人可以从本书获益? - **数据库管理员**:可以从中学习到最佳实践和技术细节。 - **软件开发人员**:...

    状态空间模型工具箱The State Space Models toolbox for MATLAB原文

    这些功能使得状态空间模型工具箱成为一个全面的MATLAB平台上的时间序列分析通用工具箱。用户可以利用MATLAB内置的图形绘制和矩阵计算功能,这些是MATLAB的核心优势之一,为时间序列分析提供了强大的后端支持。 状态...

    锂离子电池的SOC估算

    在电池SOC预测中,EKF能够处理电池的非线性动力学特性,并通过递归的方式对SOC进行最优估计。EKF算法的基本步骤包括预测阶段和更新阶段,能够根据观测到的电池电压、电流等数据不断调整SOC的估计值。 ##### 2. EKF...

    时变时滞非线性动力系统的递归神经网络辨识与控制设计的通用过程

    4. 通用过程:文档提及的是一个通用的设计过程,这意味着该过程可以适用于不同的时变时滞非线性动力系统。这个过程可能包括数据收集、系统建模、控制策略设计、仿真测试等步骤,并且应该是灵活且具有广泛适用性的。 ...

    非线性最小二乘优化matlab程序

    2. `lsqnonlin`:这是一个更通用的函数,适用于任何非线性最小二乘问题。它采用梯度下降或牛顿法等优化算法,对目标函数进行迭代优化,寻找最小值。 三、非线性最小二乘优化的算法 1. 梯度下降法:通过沿着目标函数...

    数据模型资源手册PDF版

    - **通用数据模型的应用**:书中强调了通用数据模型的重要性,即一种适用于所有企业的数据模型设计理念,有助于降低定制化成本,提高复用率。 #### 三、核心概念与术语 - **实体**:数据模型中的基本组成部分之一,...

    分布式水文模型的GPU并行化及快速模拟技术.pdf

    3. CUDA并行计算框架:NVIDIA公司提出的CUDA(Compute Unified Device Architecture)是一种并行计算平台和编程模型,它使开发者能够利用NVIDIA的GPU进行通用计算。CUDA的出现使得GPU编程变得更加方便,从而在并行...

    数据模型资源手册卷1

    因此,《数据模型资源手册卷1》应运而生,它旨在为企业提供一套通用的数据模型框架,帮助解决上述问题。 #### 谁能从这本书中受益? - **IT专业人员**:特别是那些负责数据库设计、开发和维护的技术人员可以从本书...

    自我调节通用人工智能 .pdf

    他提出了几种条件下,回形针末日可能发生的情形,并通过构建模型展示了在某些特定的递归自改进架构下,一个以生产回形针为目标的AI实际上可能会阻止自身开发过强的力量能力。 #### 模型分析 ##### 控制问题 冈斯...

Global site tag (gtag.js) - Google Analytics