Python数据结构之递归方法怎么用
Python数据结构之递归方法怎么用
这篇“Python数据结构之递归方法怎么用”文章的知识点大部分人都不太理解，所以小编给大家总结了以下内容，内容详细，步骤清晰，具有一定的借鉴价值，希望大家阅读完这篇文章能有所收获，下面我们一起来看看这篇“Python数据结构之递归方法怎么用”文章吧。
1.学习目标
递归函数是直接调用自己或通过一系列语句间接调用自己的函数。递归在程序设计有着举足轻重的作用，在很多情况下，借助递归可以优雅的解决问题。本节主要介绍递归的基本概念以及如何构建递归程序。
2.递归
2.1递归的基本概念
递归是一种解决问题的方法，它将问题不断的分为更小的子问题，通过处理普通的子问题来解决问题。递归函数是直接调用自己或通过一系列语句间接调用自己的函数。需要注意的是，递归函数每次调用自己时，都会将原问题进行简化，最终较小问题的序列必须收敛于基本情况，解决问题，终止递归。利用递归可以非常优雅的解决一些复杂问题。很多数学函数就是递归定义的，比如使用递归定义的阶乘函数：
尽管这个定义是递归的，但它不是无限循环无法终止的。事实上，利用此函数可以非常简单的计算阶乘。例如计算3!，根据定义，有3!=3(3–1)!=3(2!)，接下来我们需要解决2!，再次应用定义 3! = 4(2!) = 3[(2)(2−1)!] = 3(2)(1!)，继续此过程，最后我们需要计算0!，而根据定义0!=1，计算过程就结束了：
3!=3(2!)=3(2)(1!)=3(2)(1)(0!)=3(2)(1)(1)=6
可以看到，递归定义并非是无限循环的，因为每次应用定义，程序都会将问题分解为更简单的子问题，在阶乘函数示例中，即为计算较小数的阶乘，直到计算0!，这不需要再次应用递归即可求解。当递归到底时，我们得到一个可以直接计算的闭合表达式，也被称为递归的“基本情况”。而函数调用自身来执行子任务时，被称为“递归情况”。
2.2递归的重要性
递归函数是从数学中借鉴的一种重要的编程技术，通常使用递归可以极大的降低代码量，在许多可以分解为子问题的任务中非常有用，例如，排序、遍历和搜索等通常可以借助递归方法快速的给出解决方案。
2.3递归三原则
和许多算法一样，递归同样有着需要遵守的重要原则，称为递归三原则：
递归算法必须有基本情况
递归算法必须改变状态并逐渐收敛于基本情况
递归算法必须包含递归情况，能够递归的调用自身
需要注意的是，递归的核心思想并不是循环，而是将问题分解成更小、更容易解决的子问题。
2.4递归的应用
递归在程序设计中有着十分重要的作用，以下是一些常用到递归的实际场景：
斐波那契数列、阶乘计算等数学问题
归并排序、快速排序
二分查找
树和图的遍历以及相关问题
汉诺塔
3.递归示例
本节中，我们将从简单的列表求和问题入手，了解递归算法的使用方式，然后再了解如何解决经典递归问题——汉诺塔。
3.1列表求和
列表求和是十分简单的问题，用来了解递归算法的思想再合适不过了。例如我们需要计算列表 [1, 2, 3, 4, 5] 的和，如果利用循环函数计算，则可以编写如下代码计算列表中所有数之和：
defsum_list(list_data):result=0foriinrange(list_data):result+=ireturnresult
如果不使用循环，我们该如何解决这一问题呢？我们可以写出求和过程((((1+2)+3)+4)+5)，而根据加法交换律，计算过程也可以写为(1+(2+(3+(4+5))))，这时我们就可以很清楚的看到，列表的数据总和等于列表第一个元素加上其余元素：
使用 python 实现以上等式如下：
defsum_list(list_data):iflen(num_list)==1:returnlist_data[0]else:returnlist_data[0]+sum_list(list_data[1:])
在代码中，首先给出了函数退出的条件，这就是递归函数的基本情况，在示例中就是说，长度为 1 的列表，其元素和就是列表中的数。不满足退出条件，sum_list 则会调用自己，这就是递归函数的递归情况，也是其称为递归函数的原因。
在下图(a)中，可以看到求解 [1, 2, 3, 4, 5] 时的递归调用过程，每次递归调用都是在解决一个更接近基本情况的问题，直到问题不能被进一步简化。
当问题无法简化时，开始拼接所有子问题的解，下图(b)展示递归函数 sum_list 在返回一系列调用结果时所进行的加法操作，当返回到顶层时，就解决了最初的问题。
3.2汉诺塔(Towers of Hanoi)问题
汉诺塔(Towers of Hanoi)是一道十分经典的谜题。它由三个塔和许多不同尺寸的圆盘组成，这些圆盘可以移动到任何杆上。开始时圆盘按尺寸升序排列在一个塔上，顶部的圆盘最小，底部圆盘最大。谜题的目标是将叠好的圆盘移动到另一个杆，且满足以下规则：
一次只能移动一个圆盘
较大圆盘不能放在较小的圆盘上
接下来我们讲解如何借助一根中间塔 Auxiliary，将高度为 n 的一叠圆盘从起始塔 Source 移到终点塔 Destination：
借助终点塔 Destination，将顶部的 n - 1 个圆盘从 Source 移动到 Auxiliary
将第 n 个圆盘从 Source 塔移动到终点塔 Destination
借助 Source 塔，将 n - 1 个磁盘从辅助塔 Auxiliary 移动到终点塔 Destination
只要遵循汉诺塔的移动规则，就可以递归地执行上述步骤。最简单的汉诺塔是只有一个盘子，在这种情况下，只需将这个盘子移到终点柱子 Destination 即可，这就是基本情况。上述递归步骤通过逐渐减小高度 n 来向基本情况靠近，如下图所示：
算法的关键在于进行两次递归调用，第一次递归是将除了最后一个圆盘以外的其他所有圆盘从 Source 塔移到辅助塔 Auxiliary 。然后将最后一个圆盘移到终点塔 Destination。第二次递归是将圆盘从 Auxiliary 移到 Destination：
deftowersOfHanoi(number,source=1,destination=3,auxiliary=2):ifnumber>=1:towersOfHanoi(number-1,source,auxiliary,destination)print("Movedisk%dfromtower%dtotower%d"%(number,source,destination))towersOfHanoi(number-1,auxiliary,destination,source)towersOfHanoi(number=3)
程序输出如下所示：
Move disk 1 from tower 1 to tower 3
Move disk 2 from tower 1 to tower 2
Move disk 1 from tower 3 to tower 2
Move disk 3 from tower 1 to tower 3
Move disk 1 from tower 2 to tower 1
Move disk 2 from tower 2 to tower 3
Move disk 1 from tower 1 to tower 3
以上就是关于“Python数据结构之递归方法怎么用”这篇文章的内容，相信大家都有了一定的了解，希望小编分享的内容对大家有帮助，若想了解更多相关的知识内容，请关注恰卡编程网行业资讯频道。