递归是一种很常见的解决问题办法,比如求解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