文档章节

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

gaomq
 gaomq
发布于 2017/06/02 16:16
字数 1628
阅读 11
收藏 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
粉丝 3
博文 59
码字总数 23993
作品 0
合肥
程序员
私信 提问
尾递归是个什么鬼

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

zhanggui
2017/10/24
0
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
0
递归算法经典实例小结(C#实现)

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

雲霏霏
2015/02/04
0
0
数据结构与算法之递归和分治思想

一、递归 1.递归的定义 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法叫做递归, 它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解,递归策略...

aibinxiao
07/01
0
0
赚他一个亿,很简单,只需要赚一块钱,跟一个亿减去一块钱

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

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

没有更多内容

加载失败,请刷新页面

加载更多

特斯拉车主成功破解了自己Model 3汽车

据汽车博客Electrek消息,一位特斯拉车主成功破解了自己Model 3汽车,还在此基础上运行了Ubuntu。 这位叫trsohmers的网友表示,“功劳大多要归到Ingineerix的头上,他花了数月才找到初始的那...

linuxCool
13分钟前
0
0
Gitbook : random errors when using gitbook plugin on running "gitbook serve"

在执行gitbook serve时,会有不定的失败错误 参考问题 :#1309 解决方案: 更新gitbook版本,这个问题似乎是3版本的问题 , 官方也不打算在这个版本解决了。 更新 到最新版本后, 不再出现问...

ol_O_O_lo
27分钟前
0
0
提灯照暗,向内自省——《中国文化的深层结构》读书笔记3800字

提灯照暗,向内自省——《中国文化的深层结构》读书笔记3800字: 作者:王健茜;断断续续一个多月才读完了《中国文化的深层结构》,这并不是一本难懂的书,之所以读得慢,源于对书中观点的思...

原创小博客
30分钟前
0
0
高德地图-行政区域接口

1、获取全国各省信息 https://restapi.amap.com/v3/config/district?extensions=all&key=应用Key&s=rsv3&output=json 2、获取下级行政区域信息 https://restapi.amap.com/v3/config/distric......

voole
42分钟前
3
0
集群介绍 ..

12月19日任务 18.1 集群介绍 18.2 keepalived介绍 18.3/18.4/18.5 用keepalived配置高可用集群 一.集群介绍 根据功能划分为两大类:高可用和负载均衡 高可用集群通常为两台服务器,一台工作,...

hhpuppy
今天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部