递推 递归 迭代 三者间有什么区别?

Question

递推 递归 迭代 三者间有什么区别?

Answer 1

简单来说，递推和迭代是类似的，是自己控制重小算到大。

fib = [0] * 100
fib[0] = 1
fib[1] = 1
for idx,_ in enumerate(fib):
    if idx > 1:
        fib[idx] = fib[idx -1] +fib[idx -2]

而递归是由程序控制，并且一般都有递归次数的限制，防止无限循环。

def fib(n):
    if n < 2:
        return 1
    else:
        return fib(n-1) + fib(n-2)

Answer 2

递归是自顶向下逐步拓展需求，最后自下向顶运算。即由f(n)拓展到f(1)，再由f(1)逐步算回f(n)
迭代是直接自下向顶运算，由f(1)算到f(n)。
递归是在函数内调用本身，迭代是循环求值。

分别用递归法和迭代法求斐波那契数列：

//使用递归的方法实现  
   
long long fibonacci_recursive(int n) {  
    if (n <= 0)  
        return 0;  
    if (n == 1)  
        return 1;  
    return fibonacci_recursive(n - 2) + fibonacci_recursive(n - 1);  
}  
   
   
   
//使用迭代的方法实现  
   
long long fibonacci_iteration(int n) {  
    int result[2] = { 0, 1 };  
    int i = 2;  
    long long num = 0;  
    if(n < 2) {  
        return result[n];  
    }  
    long long fib_minusone = 1;  
    long long fib_minustwo = 0;  
    for(;i <=n;i++) {  
        num = fib_minusone + fib_minustwo;  
        fib_minustwo = fib_minusone;  
        fib_minusone = num;  
    }  
    return num;  
}