把它写成递归，或者作为练习，可能会很有趣。

但是，如果要在生产中使用该代码，则需要考虑堆栈溢出的可能性。

尾递归优化可以消除堆栈溢出，但是您是否想要经历这样的麻烦，并且您需要知道您可以指望它在您的环境中进行优化。

每次算法递归，数据大小或n减少了多少?

If you are reducing the size of data or n by half every time you recurse, then in general you don't need to worry about stack overflow. Say, if it needs to be 4,000 level deep or 10,000 level deep for the program to stack overflow, then your data size need to be roughly 24000 for your program to stack overflow. To put that into perspective, a biggest storage device recently can hold 261 bytes, and if you have 261 of such devices, you are only dealing with 2122 data size. If you are looking at all the atoms in the universe, it is estimated that it may be less than 284. If you need to deal with all the data in the universe and their states for every millisecond since the birth of the universe estimated to be 14 billion years ago, it may only be 2153. So if your program can handle 24000 units of data or n, you can handle all data in the universe and the program will not stack overflow. If you don't need to deal with numbers that are as big as 24000 (a 4000-bit integer), then in general you don't need to worry about stack overflow.

但是，如果每次递归时都将数据或n的大小减小一个常数，那么当n仅变为20000时，就会遇到堆栈溢出。也就是说，当n为1000时，程序运行良好，你认为程序很好，然后在未来的某个时候，当n为5000或20000时，程序堆栈溢出。

所以如果你有堆栈溢出的可能，试着让它成为一个迭代的解决方案。

在许多情况下，由于缓存提高了性能，递归更快。例如，这是一个使用传统归并例程的归并排序的迭代版本。它将比递归实现运行得慢，因为缓存改进了性能。

迭代实现

public static void sort(Comparable[] a)
{
    int N = a.length;
    aux = new Comparable[N];
    for (int sz = 1; sz < N; sz = sz+sz)
        for (int lo = 0; lo < N-sz; lo += sz+sz)
            merge(a, lo, lo+sz-1, Math.min(lo+sz+sz-1, N-1));
}

递归实现

private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi)
{
    if (hi <= lo) return;
    int mid = lo + (hi - lo) / 2;
    sort(a, aux, lo, mid);
    sort(a, aux, mid+1, hi);
    merge(a, aux, lo, mid, hi);
}

PS -这是Kevin Wayne教授(普林斯顿大学)在Coursera上的算法课程上讲的。

据我所知，Perl没有优化尾递归调用，但是您可以伪造它。

sub f{
  my($l,$r) = @_;

  if( $l >= $r ){
    return $l;
  } else {

    # return f( $l+1, $r );

    @_ = ( $l+1, $r );
    goto &f;

  }
}

第一次调用时，它将在堆栈上分配空间。然后它将改变它的参数，并重新启动子例程，而不向堆栈添加任何东西。因此，它会假装从未调用过自己，将其转变为一个迭代过程。

注意，没有“my @_;”或“local @_;”，如果你这样做，它将不再工作。

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

简而言之: 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)
}

堆栈溢出只会发生在编程语言没有内置内存管理....否则，请确保在函数(或函数调用、STDLbs等)中有一些内容。如果没有递归，就不可能有这样的东西……谷歌或SQL，或任何地方一个人必须有效地排序大型数据结构(类)或数据库。

如果你想要遍历文件，递归是一种方法，我敢肯定这就是find * | ?grep *的工作方式。有点像双重递归，特别是管道(但不要像很多人那样做一堆系统调用，如果你要把它放在那里供别人使用的话)。

高级语言，甚至clang/cpp也可以在后台实现相同的功能。

使用Chrome 45.0.2454.85 m，递归似乎要快得多。

代码如下:

(function recursionVsForLoop(global) {
    "use strict";

    // Perf test
    function perfTest() {}

    perfTest.prototype.do = function(ns, fn) {
        console.time(ns);
        fn();
        console.timeEnd(ns);
    };

    // Recursion method
    (function recur() {
        var count = 0;
        global.recurFn = function recurFn(fn, cycles) {
            fn();
            count = count + 1;
            if (count !== cycles) recurFn(fn, cycles);
        };
    })();

    // Looped method
    function loopFn(fn, cycles) {
        for (var i = 0; i < cycles; i++) {
            fn();
        }
    }

    // Tests
    var curTest = new perfTest(),
        testsToRun = 100;

    curTest.do('recursion', function() {
        recurFn(function() {
            console.log('a recur run.');
        }, testsToRun);
    });

    curTest.do('loop', function() {
        loopFn(function() {
            console.log('a loop run.');
        }, testsToRun);
    });

})(window);

结果

//使用标准for循环运行100次

循环运行100x。 完成时间:7.683ms

//使用带有尾递归的函数递归方法运行100次

100x递归运行。 完成时间:4.841毫秒

在下面的截图中，当每次测试运行300次循环时，递归再次以更大的优势获胜