本文主要是介绍数据结构【八】- 递归【一】递归的本质/ 递归的宏观语意/ 写递归算法的基本原则/ 递归函数的“微观”解读,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
一。递归的本质
本质上,递归就是将原来的问题,转化为更小的同一问题。
二。递归的举例
更多链表问题搜索:LinkedListProblems.pdf
(一)例子
用递归来写数组求和
(二)思路
1. 对一个数组求和就等于:将【数组总和】=【数组的第0个数】+【数组中从1索引到...n-1这个索引的和】。
- 这个时候,Sum(arr[1....n-1])要解决的问题就要比Sum(arr[0....n-1]要解决的问题更小。==> 这就是更小的同一问题。
- 为什么更小?==> 因为Sum(arr[1....n-1])少了一个元素,只需要对n-1个元素求和。
2. 以此类推:【Sum(arr[1....n-1])】= 【索引为1的元素】+【数组中从2索引到...n-1这个索引的和】
3. 直到在最后的时候,我们这个问题缩小到:【Sum(arr[n-1....n-1])】=【索引为n-1的元素】+【空数组】
【空数组】的和为0,至此我们得到了一个基本的问题
(三)数组求和代码
public class ArraySum {public static int sum(int[] arr){return sum(arr,0);}//计算arr[l...n]这个区间内所有数字的和private static int sum(int[] arr, int l){//基本问题:当l==arr.length的时候,也就是数组为空if (l == arr.length){return 0;}return arr[l]+sum(arr, l+1);}
}
(四)代码测试
public static void main(String[] args){int[] nums = {1,2,3,4,5,6,7,8};System.err.println(sum(nums));}
36
(四)递归函数的“微观”解读
- 递归函数的调用,本质就是函数调用。
1. 递归调用方法
对于数据arr = [6,10] ,我们用sum()方法求它的总和。
2. 递归运行过程:
我们给数组【arr = [6,10]】来调用方法 sum(arr,0);
第一步:
l此时等于0,那么我们运行到 【int x = sum(arr,l+1);】的时候,就产生了递归调用。重新调用了一下sum(arr,0+1).
第二步: l此时等于1。调用sum(arr,1),也就是在一个新的sum函数中,重新针对现在的参数走一遍。进入方法sum(arr,1),运行到 【int x = sum(arr,l+1);】的时候2产生了递归调用。重新调用了一下sum(arr,1+1).
第三步:l此时等于2。调用sum(arr,2),进入方法sum(arr,2),运行到 【if (l == arr.length) return 0;】的时候,满足这个条件,【return 0】;
第四步:此时sum(arr,2)中返回的【0】就返回到上一次在sum(arr,1)这次调用中中断的位置,也就是【int x = sum(arr,l+1);】.
此时x可以计算出来【x是0】.然后我们可以计算出sum(arr,1)的res的值【res是10+0=10】
第五步:此时sum(arr,1)中返回的【10】就返回到上一次在sum(arr,0)这次调用中中断的位置,也就是【int x = sum(arr,l+1);】。
此此时x可以计算出来【x是10】.然后我们可以计算出sum(arr,0)的res的值【res是6+10=16】
第六步:最后得出sum(arr,0)的结果是16.
三。写递归算法的基本原则
1. 所有的递归算法都可以分成两部分
- 求解最基本的问题(最基本的问题是不能自动求解的,是需要我们自己编写逻辑来求解)
- 核心部分:将原问题转化为更小的问题
2. 写递归函数的时候要注重:递归函数的“宏观”语意。站在更高的层次去思考这个函数本身的功能和作用,有利于理解递归的逻辑。
对于【数组求和】来说,我们“宏观”语意就是:计算arr[] 数组的“l”到“n”的索引的和。
对于【删除链表元素】来说,宏观语意就是:对一个链表中删除值为val的节点
3. 不要太注意内部调用。
4. 递归函数的调用,本质就是函数调用。只不过调用的函数是自己而已。
5. 递归调用是有代价的:
函数调用需要更多的时间开销,包括
【1】记录当前函数执行的位置+当前局部变量的状态,
【2】函数调用本身在计算机底层要找到新的函数所在的位置。
更重要的:递归调用消耗系统栈的空间。
【1】例如,当不处理基本问题时,递归将一直进行下去,没有终止,最终产生错误:系统栈被占满.
【2】如果对于数百万的数组用递归算法求和,栈空间不够用。
【3】如果对百万长度的链表递归删除元素,栈空间不够用。
以上所有内容都是通过"慕课网"听"liuyubobobo"的《玩转数据结构》课程后总结
这篇关于数据结构【八】- 递归【一】递归的本质/ 递归的宏观语意/ 写递归算法的基本原则/ 递归函数的“微观”解读的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!