文档章节

算法-对递归的理解-----转载

gaomq
 gaomq
发布于 2017/06/02 16:16
字数 1628
阅读 5
收藏 0
点赞 0
评论 0

为什么要用递归

编程里面估计最让人摸不着头脑的基本算法就是递归了。很多时候我们看明白一个复杂的递归都有点费时间,尤其对模型所描述的问题概念不清的时候,想要自己设计一个递归那么就更是有难度了。

很多不理解递归的人(今天在csdn里面看到一个初学者的留言),总认为递归完全没必要,用循环就可以实现,其实这是一种很肤浅的理解。因为递归之所以在程序中能风靡并不是因为他的循环,大家都知道递归分两步,递和归,那么可以知道递归对于空间性能来说,简直就是造孽,这对于追求时空完美的人来说,简直无法接接受,如果递归仅仅是循环,估计现在我们就看不到递归了。递归之所以现在还存在是因为递归可以产生无限循环体,也就是说有可能产生100层也可能10000层for循环。例如对于一个字符串进行全排列,字符串长度不定,那么如果你用循环来实现,你会发现你根本写不出来,这个时候就要调用递归,而且在递归模型里面还可以使用分支递归,例如for循环与递归嵌套,或者这节枚举几个递归步进表达式,每一个形成一个递归。

用归纳法来理解递归

数学都不差的我们,第一反应就是递归在数学上的模型是什么。毕竟我们对于问题进行数学建模比起代码建模拿手多了。 (当然如果对于问题很清楚的人也可以直接简历递归模型了,运用数模做中介的是针对对于那些问题还不是很清楚的人)

自己观察递归,我们会发现,递归的数学模型其实就是归纳法,这个在高中的数列里面是最常用的了。回忆一下归纳法。

归纳法适用于想解决一个问题转化为解决他的子问题,而他的子问题又变成子问题的子问题,而且我们发现这些问题其实都是一个模型,也就是说存在相同的逻辑归纳处理项。当然有一个是例外的,也就是递归结束的哪一个处理方法不适用于我们的归纳处理项,当然也不能适用,否则我们就无穷递归了。这里又引出了一个归纳终结点以及直接求解的表达式。如果运用列表来形容归纳法就是:

  • 步进表达式:问题蜕变成子问题的表达式
  • 结束条件:什么时候可以不再是用步进表达式
  • 直接求解表达式:在结束条件下能够直接计算返回值的表达式
  • 逻辑归纳项:适用于一切非适用于结束条件的子问题的处理,当然上面的步进表达式其实就是包含在这里面了。

这样其实就结束了,递归也就出来了。递归算法的一般形式:

void func( mode)
{
    if(endCondition)
    {
        constExpression         //基本项
    }
    else
    {
        accumrateExpreesion     //归纳项
        mode=expression         //步进表达式
            func(mode)          //调用本身,递归
    }
}
 

 

最典型的就是N!算法,这个最具有说服力。理解了递归的思想以及使用场景,基本就能自己设计了,当然要想和其他算法结合起来使用,还需要不断实践与总结了。

#include "stdio.h"
#include "math.h"

int main(void)
{
    int n, rs;

    printf("请输入需要计算阶乘的数n:");
    scanf("%d",&n);

    rs = factorial(n);
    printf("%d ", rs);
}

// 递归计算过程
int factorial(n){
     if(n == 1) {
          return 1;
     }
     return n * factorial(n-1);
}
 

第一个算法还是比较好理解的,但第二个就不那么好理解了。第一个算法的思想是:如果这个树是空,则返回0;否则先求左边树的深度,再求右边数的深度,然后对这两个值进行比较哪个大就取哪个值+1。而第二个算法,首先应该明白isB函数的功能,它对于空树返回0,对于平衡树返回树的深度,对于不平衡树返回-1。明白了函数的功能再看代码就明白多了,只要有一个函数返回了-1,则整个函数就会返回-1。(具体过程只要认真看下就明白了)求阶乘的递归比较简单,这里就不展开了。

再来两个递归的例子

返回一个二叉树的深度:

int depth(Tree t){
      if(!t) return 0; 
    else { 
        int a=depth(t.right); 
        int b=depth(t.left); 
        return (a>b)?(a+1):(b+1); 
    } 
}
 

叉树是否平衡:

int isB(Tree t){
      if(!t) return 0; 
    int left=isB(t.left); 
    int right=isB(t.right); 
    if( left >=0 && right >=0 && left - right <= 1 || left -right >=-1) 
        return (left < right)? (right +1) : (left + 1); 
    else return -1; 


对于递归,最好的理解方式便是从函数的功能意义的层面来理解。了解一个问题如何被分解为它的子问题,这样对于递归函数代码也就理解了。这里有一个误区(我也曾深陷其中),就是通过分析堆栈,分析一个一个函数的调用过程、输出结果来分析递归的算法。这是十分要不得的,这样只会把自己弄晕,其实递归本质上也是函数的调用,调用的函数是自己或者不是自己其实没什么区别。在函数调用时总会把一些临时信息保存到堆栈,堆栈只是为了函数能正确的返回,仅此而已。我们只要知道递归会导致大量的函数调用,大量的堆栈操作就可以了。

小结

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

本文转载自:http://www.nowamagic.net/librarys/veda/detail/2314

共有 人打赏支持
gaomq
粉丝 2
博文 53
码字总数 22928
作品 0
沈阳
程序员
尾递归是个什么鬼

了解尾递归之前,先了解一下尾调用。 在计算机科学里,尾调用是指一个函数里的最后一个动作是一个函数调用的情形:即这个调用的返回值直接被当前函数返回的情形。这种情形下该调用位置为尾位...

zhanggui ⋅ 2017/10/24 ⋅ 0

递归算法经典实例小结(C#实现)

一 、递归算法简介 在数学与计算机科学中,递归是指在函数的定义中使用函数自身的方法。   递归算法是一种直接或者间接地调用自身算法的过程。在计算机编写程序中,递归算法对解决一大类问...

雲霏霏 ⋅ 2015/02/04 ⋅ 0

[LeetCode] Serialize and Deserialize Binary Tree 二叉树的序列化和去序列化

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a networ......

机器的心脏 ⋅ 2017/12/15 ⋅ 0

赚他一个亿,很简单,只需要赚一块钱,跟一个亿减去一块钱

陆小凤原创 小白:陆大侠,你总算出现了,你在海边捉到了一只海龟? 海归 递归,不是海归。递归是一种很重要的结构与设计思想。 本文企图帮助你理解递归的设计与实现。 (一)递归的表现 有递...

奇哥十年程序 ⋅ 2017/11/17 ⋅ 0

[LeetCode] Serialize and Deserialize BST 二叉搜索树的序列化和去序列化

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a networ......

机器的心脏 ⋅ 2017/12/10 ⋅ 0

28个不得不看的经典编程算法

转载自:28个不得不看的经典编程算法 第一名:Union-find 严格地说,并查集是一种数据结构,它专门用来处理集合的合并操作和查询操作。并查集巧妙地借用了树结构,使得编程复杂度降低到了令人...

xjhznick ⋅ 2014/11/06 ⋅ 0

递归的入门介绍

> 陆小凤原创 > 小白:陆大侠,你总算出现了,你在海边捉到了一只海龟? 递归,不是海归。递归是一种很重要的结构与设计思想。 本文企图帮助你理解递归的设计与实现。 (一)递归的表现 有递...

奇哥3 ⋅ 2017/12/14 ⋅ 0

php递归算法

递归函数是我们常用到的一类函数,最基本的特点是函数自身调用自身,但必须在调用自身前有条件判断,否则无限无限调用下去。实现递归函数可以采取什么方式呢?本文列出了三种基本方式。理解其...

微雨初晴 ⋅ 2016/11/26 ⋅ 0

通过递归算法完成树的级联勾选的一般思路

文章版权由作者李晓晖和博客园共有,若转载请于明显处标明出处:http://www.cnblogs.com/naaoveGIS/ 1.背景 在某个项目中,发现当tree上加上checkbox后,初始化该树时会特别慢。现场树上的节...

李晓晖 ⋅ 2016/09/14 ⋅ 0

二叉树创建与遍历,递归和非递归实现

title: 二叉树最大的权值和 date: 2017-09-16 09:32:32 category: 默认分类 本文介绍 二叉树最大的权值和 二叉树最大的权值和 本文由在当地较为英俊的男子金天大神原创,版权所有,欢迎转载,...

Nicholas_Jela ⋅ 2017/09/18 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

从方法论到零售客户实践 解码阿里巴巴数据中台——2018上海云栖大会

摘要: 一、数据中台之道 6月8日,上海云栖大会进入了第二天的议程,数据中台专场论坛座无虚席,数据中台总架构师邓中华女士向在场的观众介绍了数据中台的衍生发展之道。 基于OneID、OneData...

阿里云云栖社区 ⋅ 20分钟前 ⋅ 0

Ubuntu部署django问题汇总

使用Anaconda3的Python3.6的pip安装UWSGI报错 原因是gcc版本不兼容,安装4.7并修改gccsudo apt-get install gcc-4.7sudo mv /usr/bin/gcc /usr/bin/gcc.baksudo ln -s /usr/bin/gcc-4.......

wuyaSama ⋅ 23分钟前 ⋅ 0

从方法论到零售客户实践 解码阿里巴巴数据中台——2018上海云栖大会

摘要: 一、数据中台之道 6月8日,上海云栖大会进入了第二天的议程,数据中台专场论坛座无虚席,数据中台总架构师邓中华女士向在场的观众介绍了数据中台的衍生发展之道。 基于OneID、OneData...

猫耳m ⋅ 23分钟前 ⋅ 0

Docker减肥小记

如果经常使用 docker,你会发现 docker 占用的资源膨胀很快,其中最明显也最容易被察 如何快速的清理 docker 占用的系统资源,具体点说就是删除那些无用的镜像、容器、网络和数据卷… 1、查看...

寰宇01 ⋅ 34分钟前 ⋅ 0

微信小程序中如何使用WebSocket实现长连接(含完整源码)

本文由腾讯云技术团队原创,感谢作者的分享。 1、前言 微信小程序提供了一套在微信上运行小程序的解决方案,有比较完整的框架、组件以及 API,在这个平台上面的想象空间很大。腾讯云研究了一...

JackJiang- ⋅ 42分钟前 ⋅ 0

定制库到Maven本地资源库

1.如果只有定制库的JAR文件 下载链接如下:pdf.jar 2.使用命令转换成Maven本地资源 mvn install:install-file -Dfile=/Users/manager/Downloads/clj-pdf-2.2.33.jar -DgroupId=clj-pdf -Dar......

年少爱追梦 ⋅ 46分钟前 ⋅ 0

高仿springmvc之xuchen-mvc

package org.mvc.framework.servlet; import java.io.BufferedReader; import java.io.ByteArrayInputStream; import java.io.ByteArrayOutputStream; import java.io.File; import java.io.......

徐志 ⋅ 48分钟前 ⋅ 0

关于自定义URLStreamHandler的一次踩坑

关于自定义URLStreamHandler的一次踩坑 20180625 lambo init 说明 一般自定义实现url的协议解析.方案为实现URLStreamHandler.实现其 openConnection 就可以了, 如果我们执行 new URL("xx://...

林小宝 ⋅ 49分钟前 ⋅ 0

【SM2证书】利用BC的X509v3CertificateBuilder组装X509国密证书

演示证书文件 链接: https://pan.baidu.com/s/1ijHNnMQJj7jzW-jXEVd6Gg 密码: vfva 所需jar包 <!-- https://mvnrepository.com/artifact/org.bouncycastle/bcpkix-jdk15on --> <dependenc......

小帅帅丶 ⋅ 50分钟前 ⋅ 0

用Calendar 实现 计算 一段时间的毫秒值

Calendar c=Calendar.getInstance();c.add(Calendar.MONTH, -1);int lastMonthMaxDay=c.getActualMaximum(Calendar.DAY_OF_MONTH);c.set(c.get(Calendar.YEAR), c.get(Calendar.MONTH)......

岸芷汀兰 ⋅ 54分钟前 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部