wordpress请求排除,青岛网站seo服务,连云港公司企业网站建设,9377白蛇传奇算法中会经常遇见重复执行某个任务#xff0c;那么如何实现呢#xff0c;本文将详细介绍两种实现方式#xff0c;迭代与递归。 本文基于 Java 语言。
一、迭代
迭代#xff08;iteration#xff09;#xff0c;就是说程序会在一定条件下重复执行某段代码#xff0c;直…算法中会经常遇见重复执行某个任务那么如何实现呢本文将详细介绍两种实现方式迭代与递归。 本文基于 Java 语言。
一、迭代
迭代iteration就是说程序会在一定条件下重复执行某段代码直到条件不再满足。 在 Java 语言中可以理解为就是循环遍历Java 中有多种遍历方式如 for 循环、while 循环。接下来讲解如何进行代码实现。
(一) for 循环
这个是最常见的迭代形式之一适合在预先知道迭代次数遍历次数时使用。 比如我们通过 for 循环计算1 2 ... n的结果。
public int forLoop(int n){int result 0;for (int i 0; i n; i) {result i;}return result;
} 流程图如下 (二) while 循环
与 for 循环类似while 循环也是一种实现迭代的方法。在 while 循环中程序每轮都会先检查条件如果条件为真则继续执行否则就结束循环。 比如我们通过 while 循环计算1 2 ... n的结果。
public int whileLoop(int n) {int result 0;int i 1; // 初始化条件变量while (i n) {result i;i; // 更新条件变量}return result;
}
(三) 嵌套循环
我们可以在一个循环结构内嵌套另一个循环结构每一次嵌套都是一次“升维”将会使时间复杂度提高至“立方关系”“四次方关系”以此类推。 下面以冒泡排序为例原理是从后两两对比更小的往前放。数组内位置交换不懂得话看一下我总结的另一篇文字--《位运算详解》。 public class FuXing {public static void main (String[] args) {int[] arr {9,6,1,5,2,3,4,7,8};System.out.println(排序后 Arrays.toString( bubbleSort(arr)));}/*** 冒泡排序*/public static void bubbleSort (int[] arr){// 过滤无序排序的数组if(arr null || arr.length 2){return;}// 倒序遍历所有的数for (int i arr.length - 1; i 0; i--) {//两两比较更小的往前放for (int j 0; j i; j) {if(arr[j] arr[j1]){swap(arr,j,j1);}}}}/*** 数组内位置交换*/public static void swap(int[] arr,int i ,int j){arr[i] ^ arr[j];arr[j] ^ arr[i];arr[i] ^ arr[j];}
}
二、递归
(一) 简介
递归recursion是一种算法策略通过直接或者间接地调用自身来解决问题将大问题分解成更多的子问题主要解决同一大类问题。 从数据结构角度看递归天然适合处理链表、树和图的相关问题因为它们非常适合用分治思想进行分析。 主要包含两个阶段
递程序不断深入地调用自身通常传入更小或更简化的参数直到达到“终止条件”。归触发“终止条件”后程序从最深层的递归函数开始逐层返回汇聚每一层的结果。 递归的三个重要要素须记住
终止条件用于决定什么时候由“递”转“归”。递归调用对应“递”函数调用自身。返回结果对应“归”将当前递归层级的结果返回至上一层
(二) 如何设计递归
在写一些递归算法时应该如何去操作呢这里分享一点个人经验当我们需要写一个递归程序时
找重复找到的相同的子问题找变化聚焦于某一个子问题查看变化的量通常会作为参数这时可定义函数体找出口也就是找终止条件这里注意关注返回值。
我们需要明确递归函数本身是为了做什么返回值是什么从最终想要的答案出发逐步寻找上一层的答案并且用它们构造当前层的答案。 比如我们通过递归计算1 2 ... n结果。
找重复n 的累加 n (n - 1)的累加n - 1 就是原问题的重复即子问题找变化聚焦于某一个子问题这里的变化就是 n 的自减递归参数就是 n - 1找出口当返回值为 1 时终止条件就是 n 1n 为 1 时无法计算阶乘。 代码如下
public int recursion (int n) {//终止条件if (n 1) return 1;//递递归调用int result recursion(n - 1);//归返回结果return result n;} 流程图如下 (三) 调用栈
在 Java 中递归函数每次调用自身时JVM 都会为新开启的函数分配内存以存储局部变量、调用地址和其他信息等。也就是在 Java 虚拟机栈中新生成一个栈帧。 因为栈空间是随着函数结果返回才会释放所以递归通常比迭代更加消耗内存空间。且调用递归函数会产生额外的开销因此时间效率上也会受影响。过深的递归操作可能导致栈内存溢出。 (四) 尾部递归
如果函数在返回前的最后一步才进行递归调用则该函数可以被编译器或解释器优化使其在空间效率上与迭代相当。这种情况被称为尾递归tail recursion。 递归方式 说明 普通递归 当函数返回到上一层级的函数后需要继续执行代码因此系统需要保存上一层调用的上下文。 尾递归 递归调用是函数返回前的最后一个操作这意味着函数返回到上一层级后无须继续执行其他操作因此系统无须保存上一层函数的上下文。 比如还是通过递归计算1 2 ... n结果。尾部递归的求和操作是在“递”的过程中执行的“归”的过程只需层层返回。而普通递归每层返回后都要再执行一次求和操作。 代码如下
public int tailRecursion (int n, int result) {// 终止条件if (n 0) return res;// 尾递归调用return tailRecursion(n - 1, res n);} 流程图如下 (五) 递归树
当处理与“分治”相关的算法问题时递归往往比迭代的思路更加直观、代码更加易读。以“斐波那契数列”为例。 斐波那契数列是指这样一个数列0,1,1,2,3,5,8,13,21,34… 这个数列从第3项开始 每一项都等于前两项之和求该数列的第 n 个数字。 回顾一下上面说的方法进行设计递归函数 1. 找重复原问题的重复即子问题。我们设斐波那契数列的第 n 个数字为 f(n)可得
f(3) f(2) f(1) 0f(4) f(3) f(2) 2f(n) f(n - 1) f(n - 2)
这里每一项都等于前两项之和 2. 找变化聚焦于某一个子问题查看变化的量会作为参数这时可定义函数体。
如f(n) f(n - 1) f(n - 2)这里的变化量有两个n -1 和 n - 2即分别做为入参。 函数体如下
int fib(int n) {// 递归调用 f(n) f(n-1) f(n-2)int res fib(n - 1) fib(n - 2);// 返回结果 f(n)return res;
} 3. 找出口当返回值为 1 或 2 时则会终止条件n 为 1 或 2 时无法拆分为子问题则完整函数如下。
int fib(int n) {// 终止条件 f(1) 0, f(2) 1if (n 1 || n 2) return n - 1;// 递归调用 f(n) f(n-1) f(n-2)int res fib(n - 1) fib(n - 2);// 返回结果 f(n)return res;
} 观察以上代码我们在函数内递归调用了两个函数这意味着从一个调用产生了两个调用分支。如下图所示这样不断递归调用下去最终将产生一棵层数为 n 的递归树recursion tree。 (六) 如何避免陷入递归
不知道你有没有被递归逻辑搞晕的经历递归调用步骤中经常会有很多深层操作所以我们可能会想看看每一层的返回值我们就会一层层深入的去思考下一步的逻辑随着思考层数加深就会觉得递归越来越困难心态就崩了。 递归不像迭代是正向思维是一个逆向思维的过程很多情况其实并不好理解也不清楚什么时候该用很容易被层层嵌套搞晕。 那么如何解决这种问题呢我们可以这么理解迭代是正向思维从已知去推未知也就是从最开始的已知的基础步骤不断的重复去累计直到任务完成。 而递归是未知推已知是将原问题分解成多个子问题我们并不知道子问题的解所以需要不断地通过递归分解直到分解成基本的已知的解最后在统一起来。 我们被搞晕的主要因素还是忍不住的跟随者递归函数去不断的深入思考要想避免这种情况。只要我们不再探究它内部的深层操作将所有的递归调用的操作当成一个整体相信它自己就能完成使命。 比如我们需要把大象装进冰箱一共需要几步是不是只要打开冰箱门把大象放进去然后关掉冰箱门。我们把大象放进冰箱当作终止条件而递归调用过程当作把大象我们并不需要知道大象怎么放进冰箱的即我们不需要知道递归是怎么执行的。 这样我们在看一些递归算法时可以避免陷入循环的递归逻辑中。 三、两者对比 对比维度 迭代 递归 实现方式 循环结构 函数调用自身 时间效率 效率通常较高无函数调用开销 每次函数调用都会产生开销 内存使用 通常使用固定大小的内存空间 累积函数调用可能使用大量的栈空间 适用问题 适用于简单循环任务代码直观、可读性好 适用于子问题分解如树、图、分治、回溯等代码结构简洁、清晰 尽管迭代和递归在很多情况下可以互相转化但不一定值得这样做有以下两点原因
转化后的代码可能更加难以理解可读性更差。对于某些复杂问题模拟系统调用栈的行为可能非常困难。 总之选择迭代还是递归取决于特定问题的性质。在编程实践中权衡两者的优劣并根据情境选择合适的方法至关重要。 参考
[1] 靳宇栋. Hello 算法.
