循环可以提高程序的性能。递归可以为程序员带来性能上的提升。在你的情况下，选择哪个更重要!

In C++ if the recursive function is a templated one, then the compiler has more chance to optimize it, as all the type deduction and function instantiations will occur in compile time. Modern compilers can also inline the function if possible. So if one uses optimization flags like -O3 or -O2 in g++, then recursions may have the chance to be faster than iterations. In iterative codes, the compiler gets less chance to optimize it, as it is already in the more or less optimal state (if written well enough).

在我的例子中，我试图通过使用Armadillo矩阵对象，以递归和迭代的方式来实现矩阵求幂。算法可以在这里找到…https://en.wikipedia.org/wiki/Exponentiation_by_squaring。 我的函数是模板化的，我已经计算了1,000,000个12x12矩阵的10次方。我得到了以下结果:

iterative + optimisation flag -O3 -> 2.79.. sec
recursive + optimisation flag -O3 -> 1.32.. sec

iterative + No-optimisation flag  -> 2.83.. sec
recursive + No-optimisation flag  -> 4.15.. sec

这些结果是使用gcc-4.8与c++11标志(-std=c++11)和Armadillo 6.1与Intel mkl获得的。英特尔编译器也显示了类似的结果。

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

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

递归和迭代取决于您想要实现的业务逻辑，尽管在大多数情况下可以互换使用。大多数开发人员选择递归，因为它更容易理解。

递归比迭代的任何可能定义都更简单(因此也更基本)。你可以只用一对组合子定义一个图灵完备系统(是的，在这样的系统中，甚至递归本身也是一个衍生概念)。Lambda演算是一个同样强大的基本系统，具有递归函数。但是如果你想正确地定义一个迭代，你需要更多的原语来开始。

至于代码——不，递归代码实际上比纯迭代代码更容易理解和维护，因为大多数数据结构都是递归的。当然，为了正确使用它，至少需要一种支持高阶函数和闭包的语言，以简洁的方式获得所有标准的组合子和迭代器。当然，在c++中，复杂的递归解决方案可能看起来有点丑，除非你是fc++的铁杆用户。

递归的内存开销更大，因为每次递归调用通常都需要将一个内存地址推入堆栈，以便稍后程序可以返回到那个地址。

尽管如此，在许多情况下，递归比循环更自然、更可读——比如在处理树的时候。在这些情况下，我建议坚持使用递归。