H5W3
当前位置:H5W3 > 其他技术问题 > 正文

了解Python中的递归函数

本文概述

作为一名专业的程序员, 你需要在变量, 条件语句, 数据类型, 访问说明符, 函数调用, 作用域等基础知识方面表现出色。无论你正在编写哪种程序, 它都是中间件, 无论是与Web开发还是数据科学相关的程序, 作为程序员, 你都需要在很大程度上了解这些中间件。首先, 你是一名程序员, 然后是数据科学家, Web开发人员或机器学习工程师等。

这样的基本概念就是递归, 在编写特定类型的函数时要知道这一点至关重要。你可能已经知道-“当函数调用自身时, 它称为递归。”但是幕后发生了什么?物理内存如何受递归影响?能否将其他所有函数都转换为递归函数?在本教程中, 你将找到这些基本问题的答案。具体来说, 你将学习:

  • 递归函数的基本剖析
  • 递归函数的内存表示形式:
  • 跟踪递归
  • 递归函数的时空分析
  • 在Python中实现一个简单的递归函数

递归函数剖析

在你的计算机科学或信息技术本科课程中, 你可能已经遇到过递归一词。在本节中, 你将以有趣的方式重新审视这些概念。让我们开始吧。

让我们再次回到递归的定义:”当函数调用自身时, 它称为递归”。让我们以一个示例来支持此定义:

void A(n){
    if(n>=1){
        A(n-1);
        print(n);
    }
}

你可以看到函数A()本身已被调用。这是递归的示例, 而A()是递归函数。

现在让我们研究递归函数的一些基础知识。

递归函数的基础知识:

递归函数必须包含以下两个属性:

  • 递归关系
  • 终止条件

考虑上面的代码片段以理解这些要点。显然, 该函数具有特定的重复关系:

了解Python中的递归函数1

$ n \ le 1 $是终止条件/锚点条件/基本条件, 如果满足, 递归将停止。必须指定此条件。否则, 函数将陷入无限循环。

(请注意, 以上代码段不遵循任何特定的编程语言。此处的主要目的是显示递归函数的示例。)

你现在必须在思考, 如果有更好的选择, 为什么有人会写一个递归函数?是的, 有时候, 很难跟踪递归, 但是一旦习惯了实践, 就可以在程序的可读性和变量上找到递归。递归不需要额外的变量即可执行, 但需要适当的终止条件才能停止。通常, 很难找到递归的终止条件。再说一次, “实践使你变得完美”。在本教程的后面, 你将看到如果使用递归而不是常规方法来实现程序, 那么该程序可以有多漂亮。现在, 你将继续研究递归函数的内存表示形式。

递归函数的内存表示

在本节中, 你将研究如何通过树和堆栈在内存上基本表示递归函数。让我们考虑以下递归函数A()来理解这一点:

void A(n){
    if(n>=1){
        A(n-1);
        print(n);
    }
}

你将首先了解使用树的内存表示形式。听起来可能有点困难, 但确实很简单。如果要以树状方式编写每个函数调用, 它将是什么样?

类似于以下内容?

了解Python中的递归函数2

这里需要注意几点:

  • 用A(3)调用该函数, 并在此进行4(3 + 1)个函数调用。如果将其概括化, 则如果调用A(n), 则总共需要(n + 1)个函数调用。
  • P()调用是由print(n)产生的打印件。
  • 通过A(0)函数调用停止的函数, 因为if语句(在A(0)函数调用之后)将收到n <1, 这将导致函数终止。

你首先看到了这种树状表示, 因为要在堆栈上表示递归函数, 则需要此表示。你现在将看到。

(堆栈是一种数据结构, 其元素的后进快出(LIFO)顺序)

对于堆栈表示, 你将必须以自上而下和左右的顺序遍历树。下图将使这一点变得清楚。

了解Python中的递归函数3

解释这个看起来很奇怪的东西(树)。请记住, 堆栈由两个操作组成-1.按下将元素插入到堆栈中, 然后按下2.弹出, 将元素从堆栈中提取出来。

现在, 你以自上而下和从左到右的顺序开始遍历树:

  • 每当你看到函数调用时, 就将其推入堆栈。
  • 如果看到print()/ P()调用, 那么你将相应地简单地打印相应的元素。

由于树以自上而下的方式从A(3)遍历到A(0), 因此将成为堆栈的元素:

了解Python中的递归函数4

现在开始树遍历的后半部分, 即左右顺序。每当你第二次看到函数调用时, 你都将弹出它。令人惊讶的是, 要从堆栈中弹出的堆栈的第一个元素(A(0))是进入堆栈的最后一个元素(LIFO, 还记得吗?)。现在, 以你的方式, 你将遇到三个P()调用-P(1), P(2)和P(3)。你将以遍历的方式打印它们。顺序将是:

1 2 3

最后, 当你完成遍历过程时, 堆栈将完全为空。为了更好地理解弹出操作, 这是完全弹出后的堆栈图像。

了解Python中的递归函数5

你已经看到了如何使用树和堆栈将简单的递归函数表示到内存中。现在, 你将看到如何跟踪递归。

跟踪递归

在本节中, 你将学习如何系统地跟踪递归。考虑以下递归函数:

void A(n){
    if(n>0){
        print(n-1);
        A(n-1);
    }
}

这里的一个关键点是每当在内存中创建一个称为激活记录的函数时, 该记录包含该函数的局部变量和一个指令指针(表示调用返回该函数时要执行的下一个任务)。将一个称为main()的函数称为上述函数A()作为A(3)。让我们对if语句中的A()行进行编号, 以更好地理解:

void A(n){
    1. if(n>0)
    2. {
        3. print(n-1);
        4. A(n-1);
    5. }
}

激活记录如下所示:

了解Python中的递归函数6

如前所述, 这些函数具有局部变量和指令指针的副本(在本例中为行号)。在A(0)之后, 函数A()将终止弹出操作。请注意, 此处使用的是水平堆栈, 该堆栈与你之前在教程中看到的堆栈完全相同。将记录推入堆栈时, 还将进行打印并打印以下元素:

2 1 0

此处必须注意指令指针, 因为在递归函数中, 控件通常转到相同的函数, 但变量值不同。因此, 保持所有这些同步确实有用。你可以按照此确切过程进行操作, 以便使用树表示形式跟踪递归。

现在, 你将学习如何对递归函数进行时空分析。

递归函数的时空分析

srcmini上有一篇关于Python渐近分析的出色文章, 建议你在阅读本节之前先进行检查。让我们快速回顾一下函数的时空分析(也称为空间复杂度和时间复杂度)的含义:

对于给定的输入, 一个函数应该产生某种输出。为了做到这一点, 该函数需要花费多少时间?时间复杂性测度接近此时间, 也称为函数的运行时。类似地, 空间复杂度度量近似于函数的空间(内存)需求, 即对于给定的输入。但是, 为什么甚至需要这些?

  • 你不必在大小可变的输入范围上运行函数, 而是可以轻松估算函数在大小不同的不同输入上的行为方式。
  • 如果你有两个函数都实现相同的目标, 那么你将采用哪个函数?你会考虑采取哪些措施来做出决定?是的, 你猜对了。你将通过分析它们的空间和时间复杂性来比较它们, 并查看哪个性能更好。

现在让我们使用一个简单的递归函数, 并分析其空间和时间复杂度。

void A(n){
    if(n>1) // Anchor condition
    {
       return A(n-1);
    }
}

首先让我们进行时间复杂度分析。假定上述函数A()花费的总时间为$ T(n)$。现在, $ T(n)$是n大于1进行比较所花费的时间与执行A(n-1)所花费的时间的总和。因此, $ T(n)$可以表示为-

$ T(n)$ = 1 + $ T(n-1)$

1是比较所需的时间(你可以在其中放置任何常量)。现在, 执行A(n-1)的时间是多少(以$ T(n)$表示)?

$ T(n-1)$ = 1 + $ T(n-2)$

同样,

$ T(n-2)$ = 1 + $ T(n-3)$

等等。

如果你密切注意这些方程, 它们都已连接。不是吗如果你一个接一个地替换它们, 则会得到-

$ T(n)$ = 1 +(1 + $ T(n-2)$)= 2 + $ T(n-2)$ = 3 + $ T(n-3)$ = …. = k + $ T(nk)$(在为k个项运行函数之后)

现在, 你需要确定该函数将在什么时候停止。根据给出的锚点条件, 你可以编写-

了解Python中的递归函数7

假设在运行了k个条件后, 该函数停止运行。如果是这样, 那么它必须是-

$ n-k = 1 => k = n-1 $

现在将k(= n -1)的值替换为$ T(n)= k + T(n-k)$:

$ T(n)=(n-1)+ T(n-(n-1))$

$ => T(n)=(n-1)+ T(1)$

$ => T(n)= n-1 + 1 = n $ //对于T(1)仅需要比较

根据渐近分析的规则, $ T(n)= n $可以重写为$ T(n)= \ mathcal {O}(n)$。这意味着函数的时间复杂度(最差)为$ \ mathcal {O}(n)$。

你可能希望在这里放慢一点, 并仔细观察此过程的每个步骤。强烈建议你在笔和纸上执行此操作, 以便你可以了解其中的每一点。

该函数的空间复杂度分析很简单。该函数是内存中函数, 不使用任何其他变量。因此, 你可以得出结论, 函数$ \ mathcal {O}(n)$的空间复杂度。

现在, 你将所有这些放在一起, 并在Python中实现一个简单的递归函数。

在Python中实现一个简单的递归函数

你将编写一个递归函数以查找给定数字的阶乘。然后, 你将编写同一函数的迭代版本。让我们开始吧。

# Recursive function factorial_recursion()

def factorial_recursion(n):  
   if n == 1:  
       return n  
   else:  
       return n*factorial_recursion(n-1)
# Call the function

num = 7
print("The factorial of ", num, " is ", factorial_recursion(num))
The factorial of  7  is  5040

还记得编写递归函数的两个关键要素吗?

  • 递归关系
  • 终止条件

在这种情况下, 递归关系可以是-

$ f(n)= n!$

$ f(n)= n * f(n-1)$等。

终止条件是当n等于1时。

简单吧?

现在, 你将实现同一函数的迭代版本。

def factorial_iterative(num):
    factorial = 1
    if num < 0:
        print("Sorry, factorial does not exist for negative numbers")
    elif num == 0:
        print("The factorial of 0 is 1")
    else:
        for i in range(1, num + 1):
           factorial = factorial*i
        print("The factorial of", num, "is", factorial)
factorial_iterative(7)
The factorial of 7 is 5040

你可以清楚地发现两个版本之间的差异。递归版本比迭代版本更漂亮。是不是

恭喜!

你已经做到了最后。在本教程中, 你对递归函数进行了广泛的研究。从绝对的基础知识开始, 再到分析递归函数的时空复杂性, 你已涵盖了所有内容。你还看到了递归对于解决具有特定特征的问题有何好处。现在, 你应该可以使用递归来解决问题(具有递归关系和终止条件)。你可能要解决使用递归查找范围内的斐波那契数的问题。

我将坚持要求你使用递归来解决一些常见问题, 例如二进制搜索, 合并排序, 河内塔等, 并执行时空分析。这肯定会使你成为更好的程序员。

从介绍的角度来看, 你所介绍的内容已足够。但是, 如果你想研究有关递归的更多信息, 请确保你访问以下链接:

  • 递归和字典, Grimson教授
  • 动态编程可优化递归函数的性能

如果你想了解有关Python的更多信息, 请参加srcmini的免费的Python数据科学入门课程。

本文地址:H5W3 » 了解Python中的递归函数

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址