每天学习一点儿算法--递归

递归是很多算法都使用的一种编程方法。听说递归是一种十分优雅的问题解决办法,可是对于初涉递归的我,还没有形成这种独特的体会。

学习使用递归的关键在于:如何将问题分为基线条件和递归条件。

基线条件和递归条件

由于递归函数调用自己,因此编写这样的函数时很容易出错,进而导致无限循环。

例如下面这个函数:

def countdown(i):   
    """倒计时"""
    print (i)
    countdown(i-1)

假设i的初始值为3,运行上述代码后:

3, 2, 1, 0, -1, -2, .........

它会一直运行下去,(可按Ctrl+C停止)

所以,编写递归函数必须要让函数能在某个时候停止递归。

让递归函数停止递归的条件就是基线条件。

递归条件指函数调用自己;基线条件指函数不再调用自己。

现在我们给函数countdown添加基线条件:

def count_down(i):    
    """倒计时"""
    print(i)    
    if i <= 1:  # 基线条件(指函数不再调用自己)
        return
    else:  # 递归条件(指函数调用自己)
        count_down(i-1)

count_down(3)

运行结果:

3
2
1

使用递归必须就要理解一个名为“调用栈”的编程概念。因为递归函数在运行的过程中是存储在栈中的。

栈是一种数据结构,只有两种基本操作:压入(进栈)和弹出(出栈)。且遵循后进先出的规则。

计算机在内部使用的栈被称为调用栈。下面用一个函数来看看计算机如何使用调用栈:

def greet(name):    
    """问候1"""
    # greet函数问候用户,再调用了另外两个函数
    print("hello " + name + " !")
    greet2(name)
    print("getting reading to say bye...")
    bye()

这个函数问候用户,再调用了另外两个函数,这两个函数的代码如下:

def greet2(name):    
    """问候2"""
    print("how are you, " + name + " ?")

def bye():    
    """拜拜"""
    print("ok, bye!")

注释:在python中,print也是一个函数,但我们先暂且不考虑它。

假设我们调用greet(“you”)。计算机先为其分配一块内存:

接下来,打印出 hello you ! 。再调用函数greet2(“you”)。同样,计算机也为这个函数调用分配一个内存块:

然后打印出 how are you, you ? 。然后从函数调用返回。此时,栈顶的内存块被弹出:

执行完函数greet2后,回到函数greet,并从离开的地方接着往下执行:首先打印 getting ready to say bye... 。再调用函数bye:

然后打印 ok bye ! 。并从这个函数返回。

现在又回到了函数greet。由于没有别的事要做,就从函数greet返回。这个被用于存储多个函数变量的栈,称之为调用栈。

递归调用栈的另一个应用就是计算阶乘。下面是一个计算阶乘的递归函数:

def fact(x):    
    """计算阶乘的函数"""
    if x == 1:        
        return 1
    else:        
        return x * fact(x-1)

我们来分析一下调用fact(3)时,调用栈是如何变化的:

说明:

  • 使用递归不能提高程序的性能,它只是让程序更容易理解。
  • 使用栈很方便,但会占据很多的内存

尾递归

最后介绍一个尾递归。尾递归是一种高级递归,它和普通递归函数的区别在于:尾递归在函数执行的最后一步调用自身,而其他递归函数在函数的最后一步不仅调用了自身,还掺杂着其他表达式。

举个例子: 计算阶乘:

def fact(x):    
    """计算阶乘的函数"""
    if x == 1:        
        return 1
    else:        
        return x * fact(x-1)

这不是尾递归函数。

def fact(x):
    """尾递归"""    
    if x == 1:        
        return 1
    else:        
        return fact(x-1)

这就是尾递归函数。

小结

  • 递归指调用自己的函数
  • 每个递归函数都有两个条件:基线条件和递归条件
  • 栈有两种操作:压入和弹出
  • 所有的函数调用都进入调用栈

每天学习一点点,每天进步一点点。

本文分享自微信公众号 - 小白客(youcoding)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-01-10

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Python

Python中的栈溢出及解决办法

1.递归函数 在函数内部,可以调用其他函数。如果一个函数在内部调用自身本身,这个函数就是递归函数。 举个例子,我们来计算阶乘n! = 1 x 2 x 3 x ....

43940
来自专栏Java技术栈

JDK8新特性之方法引用

什么是方法引用 方法引用是只需要使用方法的名字,而具体调用交给函数式接口,需要和Lambda表达式配合使用。 如: List<String> list = Ar...

29750
来自专栏chenjx85的技术专栏

leetcode-686-Repeated String Match(重复多少次A能够找到B)

15830
来自专栏JetpropelledSnake

Python学习笔记之Python正则表达式指南

正则表达式并不是Python的一部分。正则表达式是用于处理字符串的强大工具,拥有自己独特的语法以及一个独立的处理引擎,效率上可能不如str自带的方法,但功能十分...

22010
来自专栏about云

spark开发基础之Scala详解apply方法

问题导读 1.什么情况下调用apply方法? 2.apply你认为有哪些作用? 3.方法调用属于apply什么功能? apply网上很多资料,但是总感觉总...

40660
来自专栏夏时

PHP 特色:可变变量

15340
来自专栏佳爷的后花媛

PHP基础

在线运行 PHP 中的每个代码行都必须以分号结束。分号是一种分隔符,用于把指令集区分开来。

16340
来自专栏LanceToBigData

Java常用类(一)之Object类详解

大家都知道Object是所有类的父类,任何类都默认继承Object 理论上Object类是所有类的父类,即直接或间接的继承java.lang.Object类。由...

27980
来自专栏技术博客

C#类和结构体的异同点简单总结

类和结构的异同点? 异:  1.关键字不同 一个是class,一个是struct     2.类型不同,一个是引用类型,一个是值类型(一个堆区,一个栈区)   ...

54820
来自专栏一“技”之长

JavaScript基础之二——方法与属性 原

    和编译型语言必须由类产生对象不同,JavaScript语言中并没有严格的类的界定,并且对象的属性和方法也可以进行动态的绑定。属性是对象中封装的一些值数据...

7420

扫码关注云+社区

领取腾讯云代金券