递归，递推，迭代的区别

刺骨的言语ヽ痛彻心扉 2022-12-14 03:48 197阅读 0赞

# 递归 #

1.  程序调用自身的编程技巧称为递归,是函数自己调用自己。
2.  使用递归要注意的有两点：  
    递归就是在过程或函数里面调用自身；  
    在使用递归时, 必须有一个明确的递归结束条件, 称为递归出口.
3.  递归分为两个阶段:  
    递推:把复杂的问题的求解推到比原问题简单一些的问题的求解;  
    回归:当获得最简单的情况后, 逐步返回, 依次得到复杂的解。
4.  优点：代码更简洁清晰。
5.  缺点：由于递归需要系统堆栈，所以空间消耗要比非递归代码要大很多。 而且，如果递归深度太大，可能会造成栈溢出。

//递归法求第n个数的斐波那契数列

long factorial(int n)
    { 
    if(n<=2) return 1;
    if(n > 1) return factorial(n - 2) +factorial(n - 1);
    }

//递归法计算n的阶乘

long factorial(int n)
    { 
    if (n <= 0) return 1;
    else return n*factorial(n - 1);
    }

# 迭代 #

1.  简单来说，其实就是不断地用旧的变量值，递推计算新的变量值。利用变量的原值推算出变量的一个新值。如果递归是自己调用自己的话，迭代就是A不停的调用B。
2.  优点：  
    1）迭代效率高，运行时间只因循环次数增加而增加；  
    2）没什么额外开销，空间上也没有什么增加；
3.  缺点：  
    1） 不容易理解；  
    2） 代码不如递归简洁；  
    3） 编写复杂问题时困难。

***注意：*** 能用迭代的不用递归，递归调用函数，浪费空间，并且递归太深容易造成堆栈的溢出。

//迭代法计算n的阶乘

long factorial(int n)
    { 
    	int result = 1;
    	while (n > 1)
    	{ 
    		result *= n;
    		n -= 1;
    	}
    	return result;
    }

# 递推 #

1.  递推算法是一种简单的算法，即通过已知条件，利用特定关系得出中间推论，直至得到结果的算法。递推算法分为顺推和逆推两种。
2.  相对于递归算法,递推算法免除了数据进出栈的过程，也就是说,不需要函数不断的向边界值靠拢,而直接从边界出发,直到求出函数值。

#define size 20
    	int main()
    	{ 
    		//循环法
    		int arr[size];
    		arr[0] = 0;
    		arr[1] = 1;
    		for (int i = 0; i <= size; i++)
    		{ 
    		if (i>1) arr[i] = arr[i - 2] + arr[i - 1];//递推算法
    		printf("factorial[%d]=%d\n", i, arr[i]);
    		}
    		system("pause");
    		return 0;
    	}

[递归，递推，迭代的区别][Link 1]  
[迭代法、数学归纳法、递归][Link 2]  
[数学归纳法：如何用数学归纳提升代码的运行效率？][Link 3]  
[高考数列通项公式解题方法（5）：迭代法、数学归纳法][5]  
[程序员的数学基础课 迭代法（自我提升第十三天）][Link 4]  
[程序员的数学基础课 数学归纳法（自我提升第二十一天）][Link 5]  
[递归式求时间复杂度的代入法与迭代法的举例讲解][Link 6]  
[递归法][Link 7]

[Link 1]: https://blog.csdn.net/weizhengbo/article/details/61053373
[Link 2]: http://www.daileinote.com/computer/math/03
[Link 3]: https://blog.csdn.net/william_n/article/details/102585383
[5]: https://zhuanlan.zhihu.com/p/103593807
[Link 4]: https://blog.csdn.net/langwang_100/article/details/106784036
[Link 5]: https://blog.csdn.net/langwang_100/article/details/107020852
[Link 6]: https://blog.csdn.net/wordwarwordwar/article/details/40106753
[Link 7]: https://www.jianshu.com/p/126c2f632503