数据结构【八】- 递归【一】递归的本质/ 递归的宏观语意/ 写递归算法的基本原则/ 递归函数的“微观”解读

本文主要是介绍数据结构【八】- 递归【一】递归的本质/ 递归的宏观语意/ 写递归算法的基本原则/ 递归函数的“微观”解读,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

一。递归的本质

            本质上,递归就是将原来的问题,转化为更小的同一问题。

二。递归的举例

更多链表问题搜索: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"的《玩转数据结构》课程后总结

这篇关于数据结构【八】- 递归【一】递归的本质/ 递归的宏观语意/ 写递归算法的基本原则/ 递归函数的“微观”解读的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/727292

相关文章

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

基本知识点

1、c++的输入加上ios::sync_with_stdio(false);  等价于 c的输入,读取速度会加快(但是在字符串的题里面和容易出现问题) 2、lower_bound()和upper_bound() iterator lower_bound( const key_type &key ): 返回一个迭代器,指向键值>= key的第一个元素。 iterator upper_bou

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

秋招最新大模型算法面试,熬夜都要肝完它

💥大家在面试大模型LLM这个板块的时候,不知道面试完会不会复盘、总结,做笔记的习惯,这份大模型算法岗面试八股笔记也帮助不少人拿到过offer ✨对于面试大模型算法工程师会有一定的帮助,都附有完整答案,熬夜也要看完,祝大家一臂之力 这份《大模型算法工程师面试题》已经上传CSDN,还有完整版的大模型 AI 学习资料,朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费

6.1.数据结构-c/c++堆详解下篇(堆排序,TopK问题)

上篇:6.1.数据结构-c/c++模拟实现堆上篇(向下,上调整算法,建堆,增删数据)-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小): 2.2 C语言代码(手写堆) 2.3 C++代码(使用优先级队列 priority_queue)

【IPV6从入门到起飞】5-1 IPV6+Home Assistant(搭建基本环境)

【IPV6从入门到起飞】5-1 IPV6+Home Assistant #搭建基本环境 1 背景2 docker下载 hass3 创建容器4 浏览器访问 hass5 手机APP远程访问hass6 更多玩法 1 背景 既然电脑可以IPV6入站,手机流量可以访问IPV6网络的服务,为什么不在电脑搭建Home Assistant(hass),来控制你的设备呢?@智能家居 @万物互联