递归有一个缺点，使用递归编写的算法的空间复杂度为O(n)。 而迭代方法的空间复杂度为O(1)。这是使用迭代而不是递归的优点。 那我们为什么要用递归呢?

见下文。

有时使用递归编写算法更容易，而使用迭代编写相同的算法略难。在这种情况下，如果您选择遵循迭代方法，您将不得不自己处理堆栈。

Your performance deteriorates when using recursion because calling a method, in any language, implies a lot of preparation: the calling code posts a return address, call parameters, some other context information such as processor registers might be saved somewhere, and at return time the called method posts a return value which is then retrieved by the caller, and any context information that was previously saved will be restored. the performance diff between an iterative and a recursive approach lies in the time these operations take.

从实现的角度来看，当处理调用上下文所需的时间与执行方法所需的时间相当时，您才真正开始注意到差异。如果递归方法的执行时间比调用上下文管理部分要长，那么就采用递归方法，因为代码通常更易于阅读和理解，而且不会注意到性能损失。否则，出于效率考虑，可以进行迭代。

在很多情况下，它提供了比迭代方法更优雅的解决方案，常见的例子是遍历二叉树，所以它不一定更难维护。一般来说，迭代版本通常更快一些(在优化过程中可能会取代递归版本)，但递归版本更容易理解和正确实现。

如果我们使用循环而不是 递归或者反之，在算法中两者都可以达到相同的目的?”

Usually yes if you are writing in a imperative language iteration will run faster than recursion, the performance hit is minimized in problems where the iterative solution requires manipulating Stacks and popping items off of a stack due to the recursive nature of the problem. There are a lot of times where the recursive implementation is much easier to read because the code is much shorter, so you do want to consider maintainability. Especailly in cases where the problem has a recursive nature. So take for example:

河内塔的递归实现:

def TowerOfHanoi(n , source, destination, auxiliary):
    if n==1:
        print ("Move disk 1 from source",source,"to destination",destination)
        return
    TowerOfHanoi(n-1, source, auxiliary, destination)
    print ("Move disk",n,"from source",source,"to destination",destination)
    TowerOfHanoi(n-1, auxiliary, destination, source)

相当短，很容易读。将其与对应的迭代TowerOfHanoi进行比较:

# Python3 program for iterative Tower of Hanoi
import sys
 
# A structure to represent a stack
class Stack:
    # Constructor to set the data of
    # the newly created tree node
    def __init__(self, capacity):
        self.capacity = capacity
        self.top = -1
        self.array = [0]*capacity
 
# function to create a stack of given capacity.
def createStack(capacity):
    stack = Stack(capacity)
    return stack
  
# Stack is full when top is equal to the last index
def isFull(stack):
    return (stack.top == (stack.capacity - 1))
   
# Stack is empty when top is equal to -1
def isEmpty(stack):
    return (stack.top == -1)
   
# Function to add an item to stack.
# It increases top by 1
def push(stack, item):
    if(isFull(stack)):
        return
    stack.top+=1
    stack.array[stack.top] = item
   
# Function to remove an item from stack.
# It decreases top by 1
def Pop(stack):
    if(isEmpty(stack)):
        return -sys.maxsize
    Top = stack.top
    stack.top-=1
    return stack.array[Top]
   
# Function to implement legal
# movement between two poles
def moveDisksBetweenTwoPoles(src, dest, s, d):
    pole1TopDisk = Pop(src)
    pole2TopDisk = Pop(dest)
 
    # When pole 1 is empty
    if (pole1TopDisk == -sys.maxsize):
        push(src, pole2TopDisk)
        moveDisk(d, s, pole2TopDisk)
       
    # When pole2 pole is empty
    else if (pole2TopDisk == -sys.maxsize):
        push(dest, pole1TopDisk)
        moveDisk(s, d, pole1TopDisk)
       
    # When top disk of pole1 > top disk of pole2
    else if (pole1TopDisk > pole2TopDisk):
        push(src, pole1TopDisk)
        push(src, pole2TopDisk)
        moveDisk(d, s, pole2TopDisk)
       
    # When top disk of pole1 < top disk of pole2
    else:
        push(dest, pole2TopDisk)
        push(dest, pole1TopDisk)
        moveDisk(s, d, pole1TopDisk)
   
# Function to show the movement of disks
def moveDisk(fromPeg, toPeg, disk):
    print("Move the disk", disk, "from '", fromPeg, "' to '", toPeg, "'")
   
# Function to implement TOH puzzle
def tohIterative(num_of_disks, src, aux, dest):
    s, d, a = 'S', 'D', 'A'
   
    # If number of disks is even, then interchange
    # destination pole and auxiliary pole
    if (num_of_disks % 2 == 0):
        temp = d
        d = a
        a = temp
    total_num_of_moves = int(pow(2, num_of_disks) - 1)
   
    # Larger disks will be pushed first
    for i in range(num_of_disks, 0, -1):
        push(src, i)
   
    for i in range(1, total_num_of_moves + 1):
        if (i % 3 == 1):
            moveDisksBetweenTwoPoles(src, dest, s, d)
   
        else if (i % 3 == 2):
            moveDisksBetweenTwoPoles(src, aux, s, a)
   
        else if (i % 3 == 0):
            moveDisksBetweenTwoPoles(aux, dest, a, d)
 
# Input: number of disks
num_of_disks = 3
 
# Create three stacks of size 'num_of_disks'
# to hold the disks
src = createStack(num_of_disks)
dest = createStack(num_of_disks)
aux = createStack(num_of_disks)
 
tohIterative(num_of_disks, src, aux, dest)

Now the first one is way easier to read because suprise suprise shorter code is usually easier to understand than code that is 10 times longer. Sometimes you want to ask yourself is the extra performance gain really worth it? The amount of hours wasted debugging the code. Is the iterative TowerOfHanoi faster than the Recursive TowerOfHanoi? Probably, but not by a big margin. Would I like to program Recursive problems like TowerOfHanoi using iteration? Hell no. Next we have another recursive function the Ackermann function: Using recursion:

    if m == 0:
        # BASE CASE
        return n + 1
    elif m > 0 and n == 0:
        # RECURSIVE CASE
        return ackermann(m - 1, 1)
    elif m > 0 and n > 0:
        # RECURSIVE CASE
        return ackermann(m - 1, ackermann(m, n - 1))

使用迭代:

callStack = [{'m': 2, 'n': 3, 'indentation': 0, 'instrPtr': 'start'}]
returnValue = None

while len(callStack) != 0:
    m = callStack[-1]['m']
    n = callStack[-1]['n']
    indentation = callStack[-1]['indentation']
    instrPtr = callStack[-1]['instrPtr']

    if instrPtr == 'start':
        print('%sackermann(%s, %s)' % (' ' * indentation, m, n))

        if m == 0:
            # BASE CASE
            returnValue = n + 1
            callStack.pop()
            continue
        elif m > 0 and n == 0:
            # RECURSIVE CASE
            callStack[-1]['instrPtr'] = 'after first recursive case'
            callStack.append({'m': m - 1, 'n': 1, 'indentation': indentation + 1, 'instrPtr': 'start'})
            continue
        elif m > 0 and n > 0:
            # RECURSIVE CASE
            callStack[-1]['instrPtr'] = 'after second recursive case, inner call'
            callStack.append({'m': m, 'n': n - 1, 'indentation': indentation + 1, 'instrPtr': 'start'})
            continue
    elif instrPtr == 'after first recursive case':
        returnValue = returnValue
        callStack.pop()
        continue
    elif instrPtr == 'after second recursive case, inner call':
        callStack[-1]['innerCallResult'] = returnValue
        callStack[-1]['instrPtr'] = 'after second recursive case, outer call'
        callStack.append({'m': m - 1, 'n': returnValue, 'indentation': indentation + 1, 'instrPtr': 'start'})
        continue
    elif instrPtr == 'after second recursive case, outer call':
        returnValue = returnValue
        callStack.pop()
        continue
print(returnValue)

再说一次，递归实现更容易理解。所以我的结论是，如果问题本质上是递归的，需要操作堆栈中的项，就使用递归。

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

迭代实现

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上的算法课程上讲的。

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

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