日期：2016年11月10日

递归是一种很常见的解决问题办法，比如求解Fibonacci数列：

int Fibonacci(int n) {
    if (n <= 1) {
        return n;
    } else {
        return Fibonacci(n - 1) + Fibonacci(n - 2);
    }
}

但是递归会导致函数调用栈很深，此外有可能会有很多重复工作。比如求解Fibonacci(4)时，Fibonacci(2)，Fibonacci(1)都会被重复求值。看一下非递归解法：

int Fibonacci(int n) {
    if (n <= 1) {
        return n;
    } else {
        int fi = 0;
        int fj = 1;
        for (int i = 2; i <= n; i++) {
            int temp = fi + fj;
            fi = fj;
            fj = temp;
        }
        return fj;
    }
}

同递归方式相比，用循环迭代的方式取代了函数调用。

最后再看一下wikipedia中关于Binary search tree中查找某一元素的递归和非递归代码。
递归：

def search_recursively(key, node):
    if node is None or node.key == key:
        return node
    elif key < node.key:
        return search_recursively(key, node.left)
    else:  # key > node.key
    return search_recursively(key, node.right)

非递归：

def search_iteratively(key, node): 
    current_node = node
    while current_node is not None:
        if key == current_node.key:
            return current_node
        elif key < current_node.key:
            current_node = current_node.left
        else:  # key > current_node.key:
            current_node = current_node.right
    return None