关键区别——递归与迭代
递归和迭代可以用来解决编程问题。使用递归或迭代来解决问题的方法取决于解决问题的方式。递归和迭代的关键区别在于递归是一种在同一个函数中调用函数的机制,而迭代是重复执行一组指令,直到给定的条件为真。递归和迭代是开发算法和构建软件应用程序的主要技术。
目录
1. 概述和主要区别
2. 什么是递归
3. 什么是迭代
4. 递归与迭代的相似性
5. 并排比较-递归与表格形式的迭代
6. 摘要
什么是递归(recursion)?
当函数在函数内调用自身时,称为递归。递归有两种类型。它们是有限递归和无限递归。有限递归有一个终止条件。无限递归没有终止条件。
递归可以用计算阶乘的程序来解释。
n!=n*(n-1)!,如果n>0
n!n=1时;
参考下面的代码计算3(3)的阶乘!=3*2*1)。
intmain公司(){
int值=阶乘(3);
printf(“Factorial is%d\n”,value);
返回0;
}
内因子(intn){
如果(n==0){
返回1;
}
其他{
返回n*阶乘(n-1);
}
}
当调用factorial(3)时,该函数将调用factorial(2)。当调用factorial(2)时,该函数将调用factorial(1)。那么factorial(1)将调用factorial(0)。阶乘(0)将返回1。在上述程序中,“if块”中的n==0条件是基本条件。同样,阶乘函数被反复调用。
递归函数与堆栈相关。在C语言中,主程序可以有许多功能。所以,main()是调用函数,main程序调用的函数就是被调用函数。当函数被调用时,控制权被赋予被调用的函数。函数执行完成后,控件返回main。然后主程序继续。因此,它会创建一个激活记录或堆栈帧来继续执行。
在上面的程序中,当从main调用factorial(3)时,它在调用堆栈中创建一个激活记录。然后,在堆栈顶部创建factorial(2)堆栈帧,依此类推。激活记录保存有关局部变量等的信息。每次调用函数时,都会在堆栈顶部创建一组新的局部变量。这些堆栈帧可以减慢速度。同样,在递归中,函数调用自身。递归函数的时间复杂度是由函数被调用的次数发现的。一个函数调用的时间复杂度为O(1)。对于n个递归调用,时间复杂度为O(n)。
什么是迭代(iteration)?
迭代是一个指令块,它一次又一次地重复,直到给定的条件为真。迭代可以用“for循环”、“do while循环”或“while循环”来实现。“for loop”语法如下。
for(初始化;条件;修改){
//声明;
}
初始化步骤首先执行。这一步是声明和初始化循环控制变量。如果条件为true,则执行大括号内的语句。这些语句执行到条件为true为止。如果条件为false,则控件将转到“for循环”之后的下一个语句。在循环中执行语句之后,控件转到modify部分。它是更新循环控制变量。然后再次检查条件。如果条件为true,则将执行大括号内的语句。这样,“for循环”迭代。
在“while循环”中,循环内的语句将一直执行,直到条件为真。
while(条件){
//陈述
}
在“do while”循环中,在循环结束时检查条件。因此,循环至少执行一次。
做{
//陈述
}while(条件)
3的阶乘3使用迭代(“for loop”)如下所示。
内部主(){
intn=3,阶乘=1;
英蒂;
对于(i=1;i<=n;i++){
阶乘=阶乘*i;
}
“阶乘(printis\Factorial)”(printis-d,Factorial%n);
返回0;
}
递归(recursion)和迭代(iteration)的共同点
- 两者都是解决问题的技巧。
- 这个任务可以用递归或迭代的方式来解决。
递归(recursion)和迭代(iteration)的区别
递归与迭代 | |
递归是在同一个函数内调用函数的一种方法。 | 迭代是在给定条件为真之前重复的一组指令。 |
空间复杂性 | |
递归程序的空间复杂度高于迭代。 | 迭代的空间复杂度较低。 |
速度 | |
递归执行缓慢。 | 通常,迭代比递归快。 |
条件 | |
如果没有终止条件,则可能存在无限递归。 | 如果条件永远不会变为false,那么它将是一个无限的迭代。 |
堆栈 | |
在递归中,调用函数时,堆栈用于存储局部变量。 | 在迭代中,不使用堆栈。 |
代码可读性 | |
递归程序更具可读性。 | 迭代程序比递归程序更难阅读。 |
总结 - 递归(recursion) vs. 迭代(iteration)
本文讨论了递归与迭代的区别。两者都可以用来解决编程问题。递归和迭代的区别在于,递归是一种机制,在同一个函数中调用一个函数,然后迭代它,反复执行一组指令,直到给定的条件为真。如果一个问题可以用递归的形式来解决,那么它也可以通过迭代来解决。
下载递归vs迭代的pdf版本
你可以下载这篇文章的PDF版本,并按照引文说明离线使用。请在这里下载PDF版本递归和迭代的区别
引用
1.要点,教程。“数据结构和算法递归基础”,教程点,2017年8月15日。此处提供2.nareshtechnologies。“C函数递归| C语言教程”,YouTube,YouTube,2016年9月12日。这里有3.yusuf Shakel。“递归算法|阶乘-分步指南”,YouTube,YouTube,2013年10月14日。此处提供
2.nareshtechnologies公司。“C函数递归| C语言教程”,YouTube,YouTube,2016年9月12日。
3.优素福·沙克尔。“递归算法|阶乘-分步指南”,YouTube,YouTube,2013年10月14日。