我发现了这些方法之间的另一个不同之处。 它看起来简单而不重要，但当你准备面试时，它有一个非常重要的角色，所以仔细看。

简而言之: 1)迭代后序遍历并不容易——这使得DFT更加复杂 2)循环检查更容易递归

细节:

在递归的情况下，很容易创建前后遍历:

想象一个相当标准的问题:“当任务依赖于其他任务时，打印所有应该执行的任务以执行任务5”

例子:

    //key-task, value-list of tasks the key task depends on
    //"adjacency map":
    Map<Integer, List<Integer>> tasksMap = new HashMap<>();
    tasksMap.put(0, new ArrayList<>());
    tasksMap.put(1, new ArrayList<>());

    List<Integer> t2 = new ArrayList<>();
    t2.add(0);
    t2.add(1);
    tasksMap.put(2, t2);

    List<Integer> t3 = new ArrayList<>();
    t3.add(2);
    t3.add(10);
    tasksMap.put(3, t3);

    List<Integer> t4 = new ArrayList<>();
    t4.add(3);
    tasksMap.put(4, t4);

    List<Integer> t5 = new ArrayList<>();
    t5.add(3);
    tasksMap.put(5, t5);

    tasksMap.put(6, new ArrayList<>());
    tasksMap.put(7, new ArrayList<>());

    List<Integer> t8 = new ArrayList<>();
    t8.add(5);
    tasksMap.put(8, t8);

    List<Integer> t9 = new ArrayList<>();
    t9.add(4);
    tasksMap.put(9, t9);

    tasksMap.put(10, new ArrayList<>());

    //task to analyze:
    int task = 5;


    List<Integer> res11 = getTasksInOrderDftReqPostOrder(tasksMap, task);
    System.out.println(res11);**//note, no reverse required**

    List<Integer> res12 = getTasksInOrderDftReqPreOrder(tasksMap, task);
    Collections.reverse(res12);//note reverse!
    System.out.println(res12);

    private static List<Integer> getTasksInOrderDftReqPreOrder(Map<Integer, List<Integer>> tasksMap, int task) {
         List<Integer> result = new ArrayList<>();
         Set<Integer> visited = new HashSet<>();
         reqPreOrder(tasksMap,task,result, visited);
         return result;
    }

private static void reqPreOrder(Map<Integer, List<Integer>> tasksMap, int task, List<Integer> result, Set<Integer> visited) {

    if(!visited.contains(task)) {
        visited.add(task);
        result.add(task);//pre order!
        List<Integer> children = tasksMap.get(task);
        if (children != null && children.size() > 0) {
            for (Integer child : children) {
                reqPreOrder(tasksMap,child,result, visited);
            }
        }
    }
}

private static List<Integer> getTasksInOrderDftReqPostOrder(Map<Integer, List<Integer>> tasksMap, int task) {
    List<Integer> result = new ArrayList<>();
    Set<Integer> visited = new HashSet<>();
    reqPostOrder(tasksMap,task,result, visited);
    return result;
}

private static void reqPostOrder(Map<Integer, List<Integer>> tasksMap, int task, List<Integer> result, Set<Integer> visited) {
    if(!visited.contains(task)) {
        visited.add(task);
        List<Integer> children = tasksMap.get(task);
        if (children != null && children.size() > 0) {
            for (Integer child : children) {
                reqPostOrder(tasksMap,child,result, visited);
            }
        }
        result.add(task);//post order!
    }
}

注意，递归后序遍历不需要对结果进行后续反转。孩子先打印，你的任务最后打印。一切都很好。您可以执行递归的预顺序遍历(上面也显示了)，这将需要反转结果列表。

迭代方法并不那么简单!在迭代(一个堆栈)方法中，你只能做一个预排序遍历，所以你必须在最后反转结果数组:

    List<Integer> res1 = getTasksInOrderDftStack(tasksMap, task);
    Collections.reverse(res1);//note reverse!
    System.out.println(res1);

    private static List<Integer> getTasksInOrderDftStack(Map<Integer, List<Integer>> tasksMap, int task) {
    List<Integer> result = new ArrayList<>();
    Set<Integer> visited = new HashSet<>();
    Stack<Integer> st = new Stack<>();


    st.add(task);
    visited.add(task);

    while(!st.isEmpty()){
        Integer node = st.pop();
        List<Integer> children = tasksMap.get(node);
        result.add(node);
        if(children!=null && children.size() > 0){
            for(Integer child:children){
                if(!visited.contains(child)){
                    st.add(child);
                    visited.add(child);
                }
            }
        }
        //If you put it here - it does not matter - it is anyway a pre-order
        //result.add(node);
    }
    return result;
}

看起来很简单，不是吗?

但在一些面试中，这是一个陷阱。

It means the following: with the recursive approach, you can implement Depth First Traversal and then select what order you need pre or post(simply by changing the location of the "print", in our case of the "adding to the result list"). With the iterative (one stack) approach you can easily do only pre-order traversal and so in the situation when children need be printed first(pretty much all situations when you need start print from the bottom nodes, going upwards) - you are in the trouble. If you have that trouble you can reverse later, but it will be an addition to your algorithm. And if an interviewer is looking at his watch it may be a problem for you. There are complex ways to do an iterative post-order traversal, they exist, but they are not simple. Example:https://www.geeksforgeeks.org/iterative-postorder-traversal-using-stack/

因此，底线是:我会在面试中使用递归，这样更容易管理和解释。在任何紧急情况下，您都可以轻松地从前顺序遍历到后顺序遍历。在迭代中，你就没有那么灵活了。

我会使用递归，然后说:“好吧，但是迭代可以让我更直接地控制使用的内存，我可以很容易地测量堆栈大小，并禁止一些危险的溢出。”

递归的另一个优点——避免/注意图中的循环更简单。

例子(preudocode):

dft(n){
    mark(n)
    for(child: n.children){
        if(marked(child)) 
            explode - cycle found!!!
        dft(child)
    }
    unmark(n)
}

递归可能会更昂贵，这取决于递归函数是否是尾部递归(最后一行是递归调用)。尾递归应该被编译器识别，并优化为迭代的对应部分(同时保持代码中简洁、清晰的实现)。

我将以最有意义的方式编写算法，并且对那些不得不在几个月或几年内维护代码的可怜的傻瓜(无论是你自己还是其他人)来说是最清楚的。如果你遇到了性能问题，那就分析你的代码，然后，只有在那之后，你才能通过迭代实现来进行优化。您可能需要研究一下内存和动态编程。

你必须记住，使用太深的递归，你会遇到堆栈溢出，这取决于允许的堆栈大小。为了防止这种情况，请确保提供一些基本情况，以结束递归。

我将通过“归纳”设计一个Haskell数据结构来回答你的问题，这是递归的一种“对偶”。然后我会展示这种对偶性是如何带来好的结果的。

我们为简单树引入一个类型:

data Tree a = Branch (Tree a) (Tree a)
            | Leaf a
            deriving (Eq)

我们可以把这个定义理解为“一棵树是一个分支(包含两棵树)或一个叶子(包含一个数据值)”。叶结点是一种最小的情况。如果树不是叶子，那么它一定是包含两棵树的复合树。这些是唯一的例子。

让我们做一个树:

example :: Tree Int
example = Branch (Leaf 1) 
                 (Branch (Leaf 2) 
                         (Leaf 3))

现在，让我们假设我们想给树中的每个值加1。我们可以通过调用:

addOne :: Tree Int -> Tree Int
addOne (Branch a b) = Branch (addOne a) (addOne b)
addOne (Leaf a)     = Leaf (a + 1)

首先，请注意这实际上是一个递归定义。它将数据构造函数Branch和Leaf作为case(因为Leaf是最小值的，这是唯一可能的case)，我们可以确定函数将终止。

用迭代风格编写addOne需要什么?循环进入任意数量的分支会是什么样子?

此外，这种递归通常可以用“函子”来分解。我们可以通过定义将树变成函子:

instance Functor Tree where fmap f (Leaf a)     = Leaf (f a)
                            fmap f (Branch a b) = Branch (fmap f a) (fmap f b)

和定义:

addOne' = fmap (+1)

我们可以提出其他递归方案，例如代数数据类型的变形(或折叠)。使用变形法，我们可以这样写:

addOne'' = cata go where
           go (Leaf a) = Leaf (a + 1)
           go (Branch a b) = Branch a b

递归在某些情况下非常有用。例如，考虑查找阶乘的代码

int factorial ( int input )
{
  int x, fact = 1;
  for ( x = input; x > 1; x--)
     fact *= x;
  return fact;
}

现在用递归函数来考虑这个问题

int factorial ( int input )
{
  if (input == 0)
  {
     return 1;
  }
  return input * factorial(input - 1);
}

通过观察这两个，我们可以看到递归很容易理解。 但如果不小心使用，它也会很容易出错。 假设如果我们错过了if (input == 0)，那么代码将执行一段时间，并以堆栈溢出结束。

比较递归和迭代就像比较十字螺丝刀和一字螺丝刀。在大多数情况下，你可以拆卸任何一个平头的十字螺钉，但如果你使用专为该螺钉设计的螺丝刀，那就更容易了，对吧?

有些算法只是适合递归，因为它们的设计方式(斐波那契数列，遍历树状结构等)。递归使算法更简洁，更容易理解(因此可共享和可重用)。

此外，一些递归算法使用“惰性评估”，这使得它们比迭代算法更有效。这意味着它们只在需要的时候执行昂贵的计算，而不是每次循环运行时都执行。

这应该足够让你开始了。我也会给你找一些文章和例子。

链接1:Haskel vs PHP(递归vs迭代)

下面是一个程序员必须使用PHP处理大型数据集的示例。他展示了在Haskel中使用递归处理是多么容易，但由于PHP没有简单的方法来完成相同的方法，他被迫使用迭代来获得结果。

http://blog.webspecies.co.uk/2011-05-31/lazy-evaluation-with-php.html

链接2:掌握递归

递归的坏名声大多来自于命令式语言的高成本和低效率。本文的作者讨论了如何优化递归算法，使其更快、更有效。他还介绍了如何将传统循环转换为递归函数，以及使用尾部递归的好处。我认为他的结束语总结了我的一些要点:

递归编程为程序员提供了一种更好的组织方式 以一种既可维护又逻辑一致的方式编写代码。” https://developer.ibm.com/articles/l-recurs/

链接3:递归比循环快吗?(回答)

下面是一个与你的问题类似的stackoverflow问题的答案链接。作者指出，许多与递归或循环相关的基准测试都是特定于语言的。命令式语言通常使用循环更快，使用递归更慢，函数式语言反之亦然。我想从这个链接中得到的主要观点是，在语言不可知论/情境盲目的意义上回答这个问题是非常困难的。

递归比循环快吗?