问题标签 [non-recursive]

我有功能

如何以非递归风格重写它？也许，它是实现某种算法吗？

我编写了一个代码，用于向二叉树插入按名称排序的元素泛型类型。但不要认为它是正确的。

你能建议我更正吗？

Possible Duplicate:
Recursion and Iteration

What is the difference between a recursive and a non-recursive function? Fibonacci to be exact.

I looking for answers that relate towards the time and memory.

我已经在本地签出了我从不同分支（具有完全不同的文件夹结构）合并到的 SVN 分支（我的分支）的副本。所以基本上有很多删除（旧文件）和添加（新文件）。

当我尝试将合并提交到存储库（到我的分支）时，Tortoise 说

此提交不是递归的，并且为提交选择了移动/重命名的文件夹。此类移动/重命名始终在存储库中递归执行。你还是要承诺吗？

可以继续进行此提交吗？如果没有，我应该怎么做才能没有问题？

另外，对于我添加的一些文件，我在添加后进行了更改（如果这会影响性质）。

我一直在搜索stackoverflow，但我没有找到一个令人满意的答案来解决我的问题。

Miller 的论文Recursive Make Considered Harmful在社区中广为人知。基本上，多年来我一直在使用非递归 make来管理我的项目的构建。到目前为止，我在非递归 make 方面的经验非常积极。

为了给其他人一些启发，我已经成功构建了包含大约 200 万行代码的 C++ 代码库。我能够正确管理依赖项。非递归方法的好处是我们可以利用并行构建。

我已经证明，这份报告中的数据与至少 5 个大型项目是一致的。但是我一直在手动编写/移植非递归make的makefile。

正如您可能想象的那样，对于大型项目，这涉及大量工作。此外，主要挑战是新团队成员很难理解/修改/调试现有的 makefile。

所以我的问题是：社区中是否有人知道任何可以进行非递归生成但在更高抽象级别管理生成文件的工具/脚本？我想了解是否有人编写了一些脚本或工具来从一些简单的输入规范生成最终的非递归生成文件。

我有一个练习问题让我很困惑 - 在不使用递归的情况下获取二叉树中叶节点的数量。我已经环顾四周寻找想法，我已经看到了一些诸如将节点传递给堆栈的方法，但是当有多个分支时，我不知道该怎么做。任何人都可以提供指针吗？

最近我需要实现非递归 DFS 作为更复杂算法的一部分，准确地说是 Tarjan 算法。递归实现非常优雅，但不适用于大图。当我实现迭代版本时，我对它最终变得多么不优雅感到震惊，我想知道我是否做错了什么。

迭代 DFS 有两种基本方法。首先，您可以一次将一个节点的所有子节点压入堆栈（似乎更为常见）。或者你可以只推一个。我将专注于第一个，因为这似乎每个人都是这样做的。

我在使用这个算法时遇到了各种问题，最终我意识到要有效地做到这一点，我需要的不是 1 个，不是 2 个，而是 3 个布尔标志（我不一定意味着你需要三个显式布尔变量，你可以间接存储信息通过通常是整数的变量的特殊值，但是您需要以一种或另一种方式访问​​这 3 条信息。三个标志是：1）已访问。这是为了防止孩子被非常冗余地推入堆栈。2) 完成。防止对同一节点进行冗余处理。3) 上升/下降。指示孩子是否已经被压入堆栈。伪代码如下所示：

一些注意事项：1）技术上你不需要上升/下降，因为你可以看看孩子们是否都完成了。但是在密集图中它的效率很低。

2），主要问题：访问/完成的事情似乎没有必要。这就是为什么（我认为）你需要它。在堆栈上访问它们之前，您无法标记访问过的东西。如果这样做，您可能会以错误的顺序处理事物。例如，假设 A 链接到 B 和 C，B 链接到 D，并且 D 链接到 C。然后从 A，您将 B 和 C 压入堆栈。从 B 你将 D 压入堆栈……然后呢？如果您在将它们压入堆栈时标记已访问的内容，则此处不会将 C 压入堆栈。但这是错误的，应该从 D 访问 C，而不是从图中的 A 访问（假设 A 在 C 之前访问 B）。因此，在处理它们之前，您不会标记访问过的东西。但是，您将 C 在堆栈上两次。所以你需要另一个标志来表明你已经完全完成了它，所以你不需要第二次处理 C。

我不知道如何避免这一切，以拥有一个完全正确的非递归 DFS，它支持卷绕和展开的动作。但本能地感觉很粗糙。有没有更好的办法？我在网上咨询过的几乎每个地方都对如何实际实现非递归 DFS 进行了掩饰，说可以做到并提供了一个非常基本的算法。当算法是正确的（就正确支持到同一节点的多条路径而言）很少见时，它很少正确支持在卷绕和展开时做一些事情。

我必须编写一个非递归程序来打印二叉树中给定节点的祖先（父节点）。我应该使用什么逻辑？

给定一个矩阵 [n,n] 我想找出我们可以从 [0,0] 到 [n,n] 非递归地达到多少种方式。

我的方法是

1. 创建一个结构节点来存储到目前为止行进的行、列和路径
2. 将节点添加到队列
3. 遍历队列直到不为空。增加行，增加列。添加到队列
4. 如果 row=n, col=n 则打印路径

问题

1. 是否有不同的方式来存储行、列和路径
2. 如果 n 非常大，将节点存储在 Queue 中可能会出现问题。我们怎样才能避免这种情况？

请不要我不是在寻找递归解决方案。我在许多面试论坛上看到这样的问题，所以想知道这是否是正确的方法。

下面是Node的结构和功能

以交替方式以递增顺序反转堆栈的最优雅的方式（更少的代码？）是什么？（非递归）

前任。