经典算法之递归(Recursion)_recursion算法编程-程序员宅基地

技术标签: 递归  # 经典算法及分析  

1、递归的定义

  递归:你打开面前这扇门,看到屋里面还有一扇门(这门可能跟前面打开的门一样大小(静),也可能门小了些(动)),你走过去,发现手中的钥匙还可以打开它,你推开门,发现里面还有一扇门,你继续打开,。。。, 若干次之后,你打开面前一扇门,发现只有一间屋子,没有门了。 你开始原路返回,每走回一间屋子,你数一次,走到入口的时候,你可以回答出你到底用这钥匙开了几扇门。

  循环:你打开面前这扇门,看到屋里面还有一扇门,(这门可能跟前面打开的门一样大小(静),也可能门小了些(动)),你走过去,发现手中的钥匙还可以打开它,你推开门,发现里面还有一扇门,(前面门如果一样,这门也是一样,第二扇门如果相比第一扇门变小了,这扇门也比第二扇门变小了(动静如一,要么没有变化,要么同样的变化)),你继续打开这扇门,。。。,一直这样走下去。 入口处的人始终等不到你回去告诉他答案。

2、递归的思想

  递归的基本思想是把规模大的问题转化为规模小的相似的子问题来解决。在函数实现时,因为解决大问题的方法和解决小问题的方法往往是同一个方法,所以就产生了函数调用它自身的情况。另外这个解决问题的函数必须有明显的结束条件,这样就不会产生无限递归的情况了。

这里写图片描述

3、递归的要素

(1)明确递归终止条件

  我们知道,递归就是有去有回,既然这样,那么必然应该有一个明确的临界点,程序一旦到达了这个临界点,就不用继续往下递去而是开始实实在在的归来。换句话说,该临界点就是一种简单情境,可以防止无限递归。

(2)给出递归终止时的处理办法

  我们刚刚说到,在递归的临界点存在一种简单情境,在这种简单情境下,我们应该直接给出问题的解决方案。一般地,在这种情境下,问题的解决方案是直观的、容易的。

(3)提取重复的逻辑,缩小问题规模

  我们在阐述递归思想内涵时谈到,递归问题必须可以分解为若干个规模较小、与原问题形式相同的子问题,这些子问题可以用相同的解题思路来解决。从程序实现的角度而言,我们需要抽象出一个干净利落的重复的逻辑,以便使用相同的方式解决子问题。

function recursion(大规模){
    
    if (end_condition){      // 明确的递归终止条件
        end;   // 简单情景
    }else{            // 在将问题转换为子问题的每一步,解决该步中剩余部分的问题
        solve;                // 递去
        recursion(小规模);     // 递到最深处后,不断地归来
    }
}
function recursion(大规模){
    
    if (end_condition){      // 明确的递归终止条件
        end;   // 简单情景
    }else{            // 先将问题全部描述展开,再由尽头“返回”依次解决每步中剩余部分的问题
        recursion(小规模);     // 递去
        solve;                // 归来
    }
}

4、递归的经典应用

  一道二叉树的题型,打印出根到叶等于5的所有节点:

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> g_vec;
const int target = 5;

class TreeNode 
{
public:
    int val;
    TreeNode *left, *right;
    TreeNode(int val) 
    {
        this->val = val;
        this->left = this->right = NULL;
    }
};

void ForEach(TreeNode *pNode, int target, vector<int> vec)
{
    if (!pNode->right && !pNode->left)//叶结点了
    {
        if (target - pNode->val == 0)//如果减到了0,就刚刚好
        {
            vec.push_back(pNode->val);
            g_vec.push_back(vec);//整个路径添加到vec中。
        }
        return;
    }
    vec.push_back(pNode->val);
    if (pNode->left)
        ForEach(pNode->left, target - pNode->val, vec);//注意参数的变化。
    if (pNode->right)
        ForEach(pNode->right, target - pNode->val, vec);
}

int main(int argc, char const *argv[])
{
    TreeNode root(1);
    TreeNode c1_l(2);
    TreeNode c1_r(4);
    TreeNode c2_l(2);
    TreeNode c2_r(1);
    TreeNode c3_l(1);
    TreeNode c3_r(2);

    root.left = &c1_l;
    root.right = &c1_r;
    c1_l.left = &c2_l;
    c1_l.right = &c2_r;
    c2_r.left = &c3_l;
    c2_r.right = &c3_r;

    vector<int> vec;
    ForEach(&root, target, vec);
    for (auto g : g_vec)
    {
        for (auto v : g)
            cout << v << " ";
        cout << endl;
    }
    return 0;
}

参考:https://blog.csdn.net/sinat_38052999/article/details/73303111
https://blog.csdn.net/theknotyouknow/article/details/24435291
https://blog.csdn.net/what951006/article/details/77988580

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/daaikuaichuan/article/details/80724642

智能推荐

华为鸿蒙开始陆续推送事件,万众期待!华为鸿蒙开始陆续推送,谁说只是安卓换皮?...-程序员宅基地

文章浏览阅读99次。关于华为鸿蒙系统的消息在一个月前小编就已经和大家打过招呼了。自华为官宣鸿蒙替代安卓以来,质疑声、催促声,可谓是此起彼伏。早前放出消息称,华为鸿蒙将在4月份开始推送。于是很多用户在3月份就开始眼巴巴等着。这不,虽说是姗姗来迟,但华为终是没有辜负大家。朋友们,华为已经开始陆续推送鸿蒙系统了!据悉,华为鸿蒙系统HarmonyOs已经在华为多款手机上进行推送,机型包括MateX2、Mate40系列、Mat..._华为手机开始推送鸿蒙合法吗

英语面试对话场景[进入外企的敲门砖]_别人问你 beginning position-程序员宅基地

文章浏览阅读1.1w次。 I:Interviewer(面试者) A:Applicant(求职者) 教育背景:简明扼要,实话实说尽管你在简历中对自己的教育背景作了介绍,但在面试时,面试官还有可能就此方面提问。还是事先做点准备吧。 ①I:what is your major? A:My major is Business Administration. I am especially interested i_别人问你 beginning position

Python 脚本封装成 .exe 文件_python selenium封装成体积最小的exe-程序员宅基地

文章浏览阅读6.4k次,点赞3次,收藏15次。最近写了一个小小的程序,需要进行封装exe,为了简单,就直接用了pyinstaller这个模块,对于python3.6版本的童鞋来说,简直方便的不要。下面就给大家介绍一下如何用pyinstaller去封装程序为exe程序。首先,需要安装一下pip这个应用,这个已经在前面的文章中说过了,windows和linux都有请借鉴windows和linux。第二步,安装好pip之后,在cmd命令窗口..._python selenium封装成体积最小的exe

监控系统为什么要加流媒体服务器,视频监控系统为什么要使用流媒体服务器做视频分发?...-程序员宅基地

文章浏览阅读1.6k次。原因解析:1、直播视频的格式多种多样,不管是移动端还是PC端都不可能支持这么多样化格式的视频,因此流媒体服务器的首要任务就是将视频更改为统一的格式,从而解决播放器格式不统一的问题,在不改变原视频的画质情况下,更改视频格式。2、视频流也是需要加密的,在金融、教育等行业,采用一对一私密式沟通时很怕信息泄露,视频流被截取,流媒体服务器可以实现对视频流的加密,有效保护私密性强的文章或视频数据,加密后的视频..._流媒体服务器在监控系统中的作用

STM32定时器 相关函数介绍_stm32定时器函数-程序员宅基地

文章浏览阅读8.2k次,点赞12次,收藏58次。相关具体内容参考 stm32f4xx_hal_time.h几种模式函数的类型都差不多,包括基本类型(Base),输出比较(OC),输入捕获(IC),pwm(PWM),单脉冲(One_Pulse)和编码器(Encoder)。/****** xxx使用上述几种模式的英文替换即可*******/HAL_TIM_xxx_InitHAL_TIM_xxx_DeInitHAL_TIM_xx_stm32定时器函数

【线性代数】【A鹿】速解矩阵乘法_矩阵的乘法运算速记-程序员宅基地

文章浏览阅读247次。速解矩阵乘法文章目录速解矩阵乘法一、确定结果矩阵的行列个数二、分解计算三、结果合并一、确定结果矩阵的行列个数​ [A]∗[B]=[C]\begin{bmatrix}A\\\end{bmatrix}*\begin{bmatrix}B\\\end{bmatrix}=\begin{bmatrix}C\\\end{bmatrix}[A​]∗[B​]=[C​]​ 结果矩阵C的行为m,列为n:m取决于[A]的行数,n取决于[B]的列数。当m=1,n=1时,C为一个具体的数而非矩阵。(特别注意,数乘矩阵是_矩阵的乘法运算速记

随便推点

Struts2输入校验之validate输入校验方式_struts2 validate()-程序员宅基地

文章浏览阅读2.5k次。一.在Web系统项目中有大量的视图页面需要用户自行输入很多数据。这些数据的类型有很多种。为了防止某些客户的恶意输入以及对Web项目的恶意破坏,必须引入输入校验,像Windows操作系统的防火墙一样把一些垃圾数据过滤掉,挡在Web系统之外。接下来就来介绍一下validate输入校验方式:1.validate方法进行输入校验:这里直接附上一个简单的用户注册功能具体介绍利用validate方法对数字_struts2 validate()

JAVA for循环画图(包括圆形,心形)_for循环画圆-程序员宅基地

文章浏览阅读2.2k次。最近从JAVA转战C++基础东西也不敢直接不学,在听了老师的分支语句和循环语句以后想起来了以前自己上C语言课用这些东西画图形,一时感慨万千,做此笔记。实心矩形x,y分别为长和宽 public static void drawRect1(int x,int y) { for(int i=0;i<y;i++) { for(int j=0;j<x;j++) { System.out.print("*"); } System.out.println(); } }_for循环画圆

android.intent.action.DOWNLOAD_COMPLETE下载广播-程序员宅基地

文章浏览阅读4.2k次。可以参考一下android DownloadManager广播事件:下载完成、通知栏点击事件当监听了这个广播, android.intent.action.DOWNLOAD_COMPLETE,但是根本没有没有接收到这个广播。群里就有人发现 华为6.0不行 乐视可以接收到 。_android.intent.action.download_complete

vue使用MQTT连接阿里云物联网平台获取实时数据_从阿里云实时获取检测数据-程序员宅基地

文章浏览阅读1.1w次,点赞12次,收藏89次。最近在做毕业设计,网页端的话前端使用了vue3,后端是node写的数据接口,运行的话是直接在本地,作为物联网工程的毕业生,当然毕业设计是少不了传感层了,一大堆任务,前面已经完成了两个安卓app,网页的增删改查和数据的可视化(echart),接下来就是网页与硬件的对接了,硬件的话选择的是阿里云的物联网平台,之前已经在平台上创建了自己的产品了,这里具体怎么操作就不多说了,不会使用物联网平台的小伙伴可以参考一下阿里云物联网平台的使用,这里讲得还是很详细的,没有硬件的小伙伴也不用着急,阿里云提供了设备模拟器,接下._从阿里云实时获取检测数据

App设计灵感之十二组精美的旅行App设计案例_基于舒适性出行的旅游app软件工程设计-程序员宅基地

文章浏览阅读1k次。有哪些名胜古迹可以去旅行,旅行目的地的食宿如何解决,这些都可以通过旅行 App 来解决。来看看这十二组旅行 App 给你的灵感吧。① Trip time mobile app screens by Taras Migulko② Travel UI exploration - Mobile App by Zesan③ Travel service - Mobile App by Abdullah Mamun④ Travel service - Mobile App by Anastasia⑤_基于舒适性出行的旅游app软件工程设计

【测试人生】在UE4插件中启用Automation自动化测试功能_fautomationtestbase-程序员宅基地

文章浏览阅读1.9k次。UE4本身支持在前端会话中执行自动化测试功能。有了它,我们可以用C++编写对应的自动化脚本,在编辑器的生命周期中随时随地运行,测试整个研发系统的子功能。要深入了解UE4自带的自动化测试功能,可以参考自动化系统概述文章系列。而本文则介绍最简单的接入UE4自带Automation自动化测试的方法,以UnrealAutomator插件为例,提供一个最小的插件+Automation的范例按照约定,每个插件需要在Private/Tests文件夹下,建立插件名RunTests.cpp,作为自动化测试的入口。然_fautomationtestbase

推荐文章

热门文章

相关标签