经典算法之递归(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

智能推荐

SOP 1.2.0 发布,开放平台解决方案项目_weixin_34148456的博客-程序员宝宝

开发四年只会写业务代码,分布式高并发都不会还做程序员? SOP 1.1.0发布,此次更新内容如下: SOP...

常见的网络攻击手段及防御方法_weixin_33785972的博客-程序员宝宝

本文不是在教你如何去攻击他人的系统,而是客观描述了现实世界中发生的攻击事件,并向你提供了抵御这些攻击的方法。  由于这些工具可以在网上免费下载,并且它可能会损害你的系统,因此,作者在文中论述某一工具时,并不表示他默许或是推荐你使用。作者提醒:在使用这些工具时,你一定要慎重、小心,而且你必须弄清楚源代码的意思。  工具一:Password Crackers  Password Crack...

区块链教程Fabric1.0源代码分析Orderer localconfig_weixin_34049948的博客-程序员宝宝

  兄弟连区块链教程Fabric1.0源代码分析Orderer localconfig,2018年下半年,区块链行业正逐渐褪去发展之初的浮躁、回归理性,表面上看相关人才需求与身价似乎正在回落。但事实上,正是初期泡沫的渐退,让人们更多的关注点放在了区块链真正的技术之上。Fabric 1.0源代码笔记 之 Orderer #localconfig(Orde...

谷歌tts使用粤语读出内容_lyblyblyblin的博客-程序员宝宝_谷歌tts

//使用粤语 Locale locale = new Locale(“yue”,”HKG”); 为什么不是 Locale locale = new Locale(“zh”,”HK”); 我也很奇怪,我是log打印出来看它有什么,再自己找的之后也找到一些资料 这是关于语言的 ISO 639-3 Macrolanguage Mappings 资料在 http://www-01.si...

如何解决INCIAP - Create Intercompany AP Invoices Terminated By Signal 11 Error_oraclebs的博客-程序员宝宝

      在运行“Create Intercompany AP Invoices”请求时偶尔会出现这样的错误“Call inv_workflow.call_generate_cogs l_gl_ccid is 0。 /oracle/test/testappl/inv/11.5.0/bin/INCIAPProgram was terminated by signal 11”。这是因为没有在OM的O

glCullFace,GL_CULL_FACE_speedboy007的博客-程序员宝宝_gl_cull_face

http://www.dreamingwish.com/dream-2012/glcullface.htmlglCullFace:指定剔出操作的多边形面 C语言描述    void glCullFace(GLenum mode); 参数    mode  指定应剔除多边形的哪一个面,不是GL_FRONT就是GL_BACK。 说明 本函数可以禁用多边形正面

随便推点

delphi 时间格式化,动态显示时间,显示最新时间_feng12301的博客-程序员宝宝_delphi时间格式化

动态显示时间(需要Timer控制的支持,以下代码放到Timer事件中)Label1.Caption := FormatDateTime('yyyy-mm-dd   hh:mm:ss' , Now);显示当前时间(放在窗体的OnShow事件中)edit1.text:=FormatDateTime('YYYYMMDDHHMMSSZZZ',now());时间格式化Wind

Python正则表达式尽可能小的匹配(遇到第一个结束字符串就停止匹配)_zhangge3663的博客-程序员宝宝_正则尽可能少的匹配

在写爬虫爬网页的时候,经常需要爬取里面的一大块代码,比如:&lt;div&gt;..................................&lt;/div&gt;&lt;/div&gt;&lt;/div&gt;&lt;/div&gt;我们需要省略号里面的代码块,如果我们用"*"、"+"就会尽可能多的匹配,就会匹配到最后一个&lt;/div&gt;。为了实现我们的需求,我们需要尽可能小的匹配,遇到第一个合适的结束字符就返回。看下面的例子,就会很快明白了a = 'd5./;.sd

为什么有一些PDF转换成Word后是乱码?_cocowei0306的博客-程序员宝宝_pdf转换成word乱码

你是否也遇到过将PDF转换成Word后,却只是一堆乱码?为什么会出现这种情况呢?要如何解决PDF转Word却是乱码的这个问题呢?首先我们来分析下PDF转换Word后为什么会出现乱码,其实归根究底都是字体的问题,一般有以下3种情况:1、原PDF文档中的文字编码丢失或不兼容。2、用其他文档格式转换为PDF时使用了内嵌的字体。3、PDF文档制作时设置了一些文字权限或操作过程有错误等,导致反向转换时也无法顺利反编译。所以如果是由以上原因造成的转换后乱码,用软件无论转换多少次或者转换成表格或PPT等文字类文

json_to_dataset批量转化json文件,多类别标注_自律给我自由LLK的博客-程序员宝宝

json_to_dataset批量转化json文件,多类别标注import argparseimport jsonimport osimport os.path as ospimport warningsimport copyimport numpy as npimport PIL.Imagefrom skimage import ioimport yamlfrom la...

Attention 编写_聂小闲的博客-程序员宝宝

转载::https://blog.csdn.net/yiyele/article/details/81393229

再次复习java正则表达式_传奇的菜鸟的博客-程序员宝宝

字符 描述\ 将下一个字符标记为一个特殊字符、或一个原义字符、或一个 向后引用、或一个八进制转义符。例如,'n' 匹配字符 "n"。'\n' 匹配一个换行符。序列 '\\' 匹配 "\" 而 "\(" 则匹配 "("。 ^ 匹配输入字符串的开始位置。如果设置了 RegExp 对象的 Multiline 属性,^ 也匹配 '\n' 或 '\r' 之后的位置。 $ 匹

推荐文章

热门文章

相关标签