韩国麦当劳网上订餐:递归与迭代(递推)有什么区别
来源:百度文库 编辑:中科新闻网 时间:2024/09/30 00:23:33
zwu说到点子上了。
递归是自顶向下逐步拓展需求,最后自下向顶运算。即由f(n)拓展到f(1),再由f(1)逐步算回f(n)
迭代是直接自下向顶运算,由f(1)算到f(n)。
递归:程序调用的编程技巧叫做递归。递归做为一种算法在程序设计语言中广泛应用。
一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法,通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解,递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算,大大地减少了程序的代码量。
递推:递推算法是一种用若干步可重复的简运算(规律)来描述复杂问题的方法。递推是序列计算机中的一种常用算法。按照一定的规律来计算序列中的每个项,通常是通过计算机前面的一些项来得出序列中的指定象的值。
迭代:迭代是重复反馈过程的活动,其目的通常是为了逼近所需目标或结果。每一次对过程的重复称为一次“迭代”。从理论上说,所有的递归函数都可以转换为迭代函数,反之亦然,然而代价通常都是比较高的。当递归次数较多时,内存占用也会随之增加。
递归与递推的区别:
递归整体是分为两步的:1.向下递推直到限制条件到了。2.回溯结果。
递推:从初始态出发,不断改变自身的过程。
递归与迭代的区别例子:
(1)分别用递归法和迭代法求阶乘
#include <stdio.h>
// 递归计算阶乘
long factorial_recursion(int n){
if(n<=0){
return 1;
}else{
return n * factorial_recursion(n-1);
}
}
// 迭代计算阶乘
long factorial_iteration(int n){
int result = 1;
while(n>1){
result *= n;
n--;
}
return result;
}
(2)分别用递归法和迭代法求斐波那契数列
//使用递归的方法实现
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;
}
归是在不断的调用,从最终态不断找到最初态,然后不断回溯的过程。
递推是没有回溯这个过程的。
递归是在函数内调用本身,迭代是循环求值,不推荐使用递归算法