python函数递归怎么理解,python写递归函数

  python函数递归怎么理解,python写递归函数

  如果一个函数可以调用自己,那么这个函数就是递归函数。本文将详细讲解Python中递归函数的用法和原理,有兴趣的可以看看。

  00-1010递归函数的条件是什么?定义一个简单的递归函数代码。分析内存堆栈区的死递归尾递归实例。

  

目录

  如果一个函数可以调用自己,那么这个函数就是递归函数。

  递归就是去,返回就是回,递归就是一劳永逸。

  

什么是递归函数

  一般来说,递归需要边界条件,整个递归结构中应该包括递归前进段递归返回段。当不满足边界条件时,递归前进,否则递归返回。也就是说,递归函数必须有边界条件来控制递归函数的前进和返回。

  

递归函数的条件

  #定义一个函数

  定义递归(数字):

  打印(数字)

  如果数量==0:

  返回“确定”

  #这个函数在自己的作用域内调用自己,这个函数是递归函数

  递归(数字-1)

  递归(10)

  结果:

  10

  九

  八

  七

  六

  五

  四

  三

  2

  一个

  0

  

定义一个简单的递归函数

  我们在执行这个函数的时候,参数被赋予了10的值,但是在执行这个函数的过程中,我们又调用了自己,所以现在这个函数会进入先执行它,再调用自己的过程,第一个调用会被暂时阻塞;

  第二次调用时,num-1,参数变为9。继续执行,然后在调用自己的代码中执行。现在它将执行第三个调用,第二个调用被阻塞。

  这是分娩的过程;

  …………

  第十一次调用时,num-1被层层嵌套,参数变成0,符合作用域中if num==0的条件判断公式。在第十一次调用中,代码被完全执行,而不是调用自己的代码,然后代码的执行返回到第十次函数调用。

  当第十个函数调用被阻塞时,达到递归(num-1),但是这一行代码结束了,也就是第十一个调用结束了,后面没有代码,所以第十个调用结束了,然后又回到第九个调用;然后第八次;是第七次,直到第一次结束,整个函数的执行才结束;

  这就是回归的过程。

  

代码解析

  栈空间就是我们常说的栈。栈是一个来回的空间,先入,后出,再出。我们在上面的例子中说过,我们的第一次调用是一个函数的第一次调用,但是第一次调用是由最后一次执行释放的,而第十一次调用是最后一次调用,第一次调用是由第一次执行释放的。这是先进先出。与堆栈空间的概念相反,队列空间是一个来回的空间,先进先出。就像我们平时排队一样,先排队的人会比后面来的人先买票。后面在研究并发的时候,我们会详细讲队列的概念。

  单栈堆是一种数据结构,栈是一种先入后出的数据结构,堆是一种排序的树型数据结构。

  堆栈区域是内存空间。栈区是先进后出的数据结构。无论是创建还是销毁,都会自动为数据分配和释放内存,这是系统自动创建的。堆是基于排序的树形数据结构,需要的数据可以先取出。无论是创建还是销毁,内存都是手动分配和释放的,由程序员手动编程。

  内存的特点:内存中的堆栈区自动分配,内存中的堆区自动释放和手动分配,手动释放时程序在内存中执行。它会因为数据类型不同而运行在内存的不同区域,不同的语言对内存分区有不同的机制。总的来说,有以下四个方面。

  :

  

  • 栈区:分配局部变量空间;
  • 堆区:是用于手动分配程序员申请的内存空间;
  • 静态区:又称之为全局栈区,分配静态变量,全局变量空间;
  • 代码区:又称之为只读区、常量区,分配常量和程序代码空间;

  上面的栈区、读取、静态区、代码区都只是内存中的一段空间。

  

  

死递归

  所以我们在使用递归函数的时候要注意,递归函数调用的过程就是一个开辟栈和释放栈的过程,调用的时候开辟栈空间,结束的时候释放栈空间,所以说,如果开辟的空间不结束就会一直存在,就会一直占用内存空间,但是栈空间是一个先进后出的空间,如果新开启的空间不释放掉,之前的空间也不会释放掉的,那么如果我们开辟的空间很多很多,但是又释放不掉,那么我们弱小的内存是否有足够的空间容纳得下这么多的栈呢?如果容纳不下,那么我们的计算机就会爆炸,所以我们在使用递归的时候要注意避免这种情况。尤其是死递归。

  每次调用函数时,在内存宗都会单独开辟一个空间,配合函数运行,这个空间叫做栈帧空间。

  1、递归是一去一回的过程,调用函数时,会开辟栈帧空间,函数执行结束之后,会释放栈帧空间,递归实际上就是不停地开辟和释放栈帧空间的过程,每次开辟栈帧空间,都是独立的一份,其中的资源不共享。

  2、触发回的过程当最后一层栈帧空间全部执行结束的时候,会触底反弹,回到上一层空间的调用处,遇到return,会触底反弹,回到上一层的调用处

  3、写递归时,必须给予递归跳出的条件,否则会发生内存溢出,可能会出现死机的情况,所以当递归的层数过多的时候,不建议使用递归。

  Python中的环境递归的层数默认为1000层左右,一般都是996层。

  

# 下面的递归函数没有跳出递归的条件,所以是一个死递归,执行看,是不是1000左右。

  def recursion(num):

   print(num)

   recursion(num+1)

  recursion(1)

  

  

  

尾递归

  简单的来说,在函数返回的时候,调用其本身,并且return语句不包含表达式,这样的一个递归函数就是一个尾递归函数。

  换句话说返回的东西就是函数本身就是尾递归函数,而递归函数只是自身调用了自身而已。

  一般情况下,尾递归的计算在参数中完成。

  我们开始的举例是一个尾递归函数吗?不是,因为那个例子这是调用了自己本省,但是并没有返回,所以还是一个普通的递归函数而已。

  使用递归的时候,我们通常在一些技术博客上看到一些关于尾递归优化的东西,这是因为尾递归无论调用多少次函数,都只会占用一份空间,只开辟一个栈帧空间,但是目前 cpython 不支持,然而最常见的解释器就是 cpython 。

  Python常见的解释器:cpython、pypy、jpython。

  尾递归相比普通递归的优点就是返回值不需要额外过多的运算。

  

  

实例

  阶乘计算

  一个正整数的阶乘是所有小于及等于该数的正整数的积,并且0的阶乘为1。

  

""" 循环计算 """

  def factorial(num):

   if num == 0:

   return 1

   elif num < -1:

   return 只能是零和正整数

   count = 1

   for i in range(1, num+1):

   count *= i

   return count

  res = factorial(5)

  print(res) # 120

  """ 使用普通递归 """

  def factorial(num):

   if num == 0:

   return 1

   elif num < -1:

   return 只能是零和正整数

   elif num == 1:

   return num

   return num * factorial(num-1) # 普通函数返回的是一个表达式

  res = factorial(5)

  print(res) # 120

  """ 使用尾递归 """

  def factorial(num, count=1):

   if num == 0:

   return 1

   elif num < -1:

   return 只能是零和正整数

   elif num == 1:

   return count

   return factorial(num-1, count*num) # 尾递归返回的是一个函数,计算式在参数中运算

  res = factorial(5)

  print(res) # 120

  

  斐波那契数列

  斐波那契数列是以0、1两个数开头,从这个数列从第3个数开始,每一个数都等于前两树之和。

  

# 使用循环解决

  def fibonacci(num):

   x, y = 0, 1

   if num < 1:

   return 输入大于0的数字

   elif num == 1:

   return 0

   elif num == 2:

   return 1

   for _ in range(num-2):

   x, y = y, y+x

   return y

  res = fibonacci(9)

  print(res) # 21

  """ 使用普通递归 """

  def fibonacci(num):

   if num < 1:

   return 输入大于0的数字

   elif num == 1:

   return 0

   elif num == 2:

   return 1

   return fibonacci(num-1) + fibonacci(num-2)

  res = fibonacci(9)

  print(res) # 21

  """ 使用尾递归 """

  def fibonacci(num, x=0, y=1):

   if num < 1:

   return 输入大于0的数字

   elif num == 1:

   return x

   elif num == 2:

   return y

   return fibonacci(num-1, x=y, y=(x+y))

  res = fibonacci(9)

  print(res) # 21

  到此这篇关于详解Python中递归函数的原理与使用的文章就介绍到这了,更多相关Python递归函数内容请搜索盛行IT软件开发工作室以前的文章或继续浏览下面的相关文章希望大家以后多多支持盛行IT软件开发工作室!

郑重声明:本文由网友发布,不代表盛行IT的观点,版权归原作者所有,仅为传播更多信息之目的,如有侵权请联系,我们将第一时间修改或删除,多谢。

留言与评论(共有 条评论)
   
验证码: