《算法图解》第三章笔记与课后练习_递归

软件环境:Python 3.7.0b4

一、基线条件和递归条件

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

def countdown(i):
  print(i)
  countdown(i-1)

countdown(5) # 测试数据

当我们编写递归函数时,必须告诉它何时停止递归。所以,每个递归函数都有两部分:

  • 基线条件(base case):函数调用自己。
  • 递归条件(recursice case):函数不再调用自己,从而避免无限循环。
def countdown(i):
  print(i)
  # 基线条件
  if i <= 0:
    return
  # 递归条件
  else:
    countdown(i-1)

countdown(5) # 测试数据

二、调用栈

计算机在内部使用被称为调用栈的栈。

def greet2(name):
    print("how are you, ", name, "?")

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

def greet(name):
    print("hello, ", name, "!")
    greet2(name)
    print("getting ready to say bye...")
    bye()

greet("adit")

调用过程如下:

  1. 假设调用greet("adit"),计算机将首先为该函数调用分配一块内存;
  2. 在这个内存中,变量name被设置为adit,并存储进这个内存中;
  3. 接下来,打印 hello,adit !,再调用greet2(name),此时的name=adit。同样,计算机也会为这个greet2函数调用分配一块内存;
  4. 计算机使用一个栈来表示这些内存块,其中第二个内存块位于第一个内存块上面。当打印 how are you,adit?,然后从函数调用返回,栈顶的内存块被弹出;
  5. 现在栈顶的内存块是函数greet,这意味刚才执行完greet2函数后返回到了函数greet里,因此当调用函数greet2时,函数greet只执行了一部分。所以我们要记住一个重要的概念:调用另一个函数时,当前函数暂停并处于未完成状态
  6. 该函数的所有变量的值都还在内存中,执行完函数greet2后,返回到函数greet中,并从离开的地方开始继续往下执行打印 getting ready to say bye...,再调用函数bye。
  7. 在栈顶添加函数bye的内存块,然后 打印 ok bye !,并从这个函数返回。
  8. 现在再次回到了函数greet,由于没有往下执行的操作,所以直接从函数greet返回。这个栈用于存储多个函数的变量,被称为调用栈。

3.1:可获得的信息有

  1. 调用了函数greet,并将参数name的值指定为maggle;
  2. 函数greet调用了函数greet2,并将参数name的值指定为maggle;
  3. 此时函数greet处于未完成状态;
  4. 当前调用的函数为greet2;
  5. 这个函数执行完毕后,函数greet将接着执行。

三、递归调用栈

def fact(x):
  if x == 1:
    return 1
  else:
    return x * fact(x-1)

使用栈的方式表述如下:

3.1:栈将不断地扩大。因为每个程序可使用的调用栈空间有限,程序用完这些空间后,将因栈的溢出而终止。

四、小结

  • 递归指的是调用自己的函数。
  • 每个递归函数都有两个条件:基线条件和递归条件。
  • 栈有两种操作:压入和弹出。
  • 所有函数调用都进入调用栈。
  • 调用栈可能非常长,所以讲占用计算机大量的内存。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏我的博客

JS闭包

在理解闭包以前.最好能先理解一下作用域链的含义,简单来说,作用域链就是函数在定义的时候创建的,用于寻找使用到的变量的值的一 个索引,而他内部的规则是,把函数自...

3315
来自专栏海天一树

小朋友学经典算法(12):分割字符串

在分割字符串之前,先来了解一些跟字符串相关的变量或函数: (1)size_type:size_type由string类类型和vector类类型定义的类型,用以保...

1232
来自专栏mukekeheart的iOS之旅

OC学习2——C语言特性之函数

1、OC是在C语言的基础上进行扩展的,在OC中直接用C语言进行coding也是可以通过编译的。因此,函数定义的语法格式如下: 函数返回值类型 函数名(形参列表...

3237
来自专栏章鱼的慢慢技术路

《算法图解》第三章笔记与课后练习

1905
来自专栏谈补锅

C语言之字符、整数、数组、字符串笔记

每种类型占用内存空间不一样,比如char占一个字节,short占2个字节,int占4个字节,double占8个字节

6393
来自专栏西安-晁州

js数组去重

对于如下对象数组 [{id: 0, name: "name1"}, {id: 1, name: "name2"},{id: 1, name: "name2"},...

2700
来自专栏GreenLeaves

C# static

本文,在大文豪的static与C#中的static随笔基础上修改,增加了几个关键知识点 1、static 关键字简介 static是C#中经常使用的关键字之一,...

1775
来自专栏老司机的技术博客

宝宝都能学会的python编程教程5:循环-2

“死循环”是必须要避免的,当然“活循环”也未必都要执行完。 break 语句 比如我们要从一个列表中找到某个特定元素,那么只要找到了这次循环就可以停止了,没有必...

3785
来自专栏黑泽君的专栏

c语言基础学习07_指针

=============================================================================

2400
来自专栏企鹅号快讯

宝宝都能学会的python编程教程5:循环-2

“死循环”是必须要避免的,当然“活循环”也未必都要执行完。 break 语句 比如我们要从一个列表中找到某个特定元素,那么只要找到了这次循环就可以停止了,没有必...

2107

扫码关注云+社区

领取腾讯云代金券