python中递归,递归python写法

　　本文主要介绍递归的基本概念以及如何构建递归程序。通过本章的学习，可以了解递归的基本概念，理解递归背后的编程思想，掌握构建递归程序的方法。有需要的可以参考一下。

　　00-1010 1.学习目标2。递归2.1递归的基本概念2.2递归的重要性2.3递归的三个原理2.4递归的应用3。递归示例3.1列表求和3.2汉诺塔问题

1.学习目标

2.递归

　　递归是解决问题的一种方法。它把问题分成更小的子问题，通过处理共同的子问题来解决。递归函数是通过一系列语句直接或间接调用自身的函数。需要注意的是，递归函数每调用一次自己，都会把原问题简单化。最后，较小问题的序列必须收敛到基本情况，解决问题并终止递归。递归可以用来优雅地解决一些复杂的问题。许多数学函数是递归定义的，例如递归定义的阶乘函数：

　　虽然这个定义是递归的，但它不是一个不能终止的无限循环。其实用这个函数计算阶乘非常简单。比如算3！根据定义，有3个！=3(31)!=3(2!)，那么我们需要解决2！再次套用定义3！=4(2!)=3[(2)(21)!]=3(2)(1!)，继续这个过程，最后我们需要计算0！而根据定义0！=1，计算过程结束：

　　3!=3(2!)=3(2)(1!)=3(2)(1)(0!)=3(2)(1)(1)=6

　　如你所见，递归定义不是无限的，因为每次应用定义时，程序都会将问题分解成更简单的子问题。在阶乘函数的例子中，计算一个较小数的阶乘，直到计算出0！无需再次应用递归即可求解。当递归到达末尾时，我们得到一个可以直接计算的封闭表达式，也称为递归的“基本情况”。当一个函数调用自己执行一个子任务时，称为“递归情况”。

2.1递归的基本概念

　　递归函数是借用数学的一种重要编程技术。通常，递归可以大大减少代码量，在许多可以分解成子问题的任务中非常有用，如排序、遍历和搜索等。通常可以通过递归快速求解。

2.2递归的重要性

　　和很多算法一样，递归也有需要遵守的重要原则，叫做递归三原则：

　　递归算法必须具备的基本情况。递归算法必须改变状态，逐渐收敛到基本情况。递归算法必须包含递归情况。需要注意的是，递归的核心思想不是循环，而是将问题分解成更小更容易解决的子问题。

2.3递归三原则

　　递归在编程中起着非常重要的作用。下面是递归中常用的一些实际场景：

　　数学问题，如斐波那契数列，阶乘计算，合并和排序，快速排序，二叉查找树和图的遍历，以及相关问题汉诺塔。

2.4递归的应用

　　在本节中，我们将从简单的列表求和问题开始，学习如何使用递归算法，然后学习如何解决经典的递归问题3354汉诺塔。

3.递归示例

　　列表求和是一个很简单的问题，理解递归算法的思想就完美了。例如，我们需要计算列表[1，2，3，4，5]的总和。如果我们使用循环函数来计算，我们可以编写下面的代码来计算列表中所有数字的总和：

　　定义总和列表(列表

　　ata):

　　 result = 0

　　 for i in range(list_data):

　　 result += i

　　 return result

　　如果不使用循环，我们该如何解决这一问题呢？我们可以写出求和过程((((1+2)+3)+4)+5)，而根据加法交换律，计算过程也可以写为(1+(2+(3+(4+5))))，这时我们就可以很清楚的看到，列表的数据总和等于列表第一个元素加上其余元素：

　　使用 python 实现以上等式如下：

def sum_list(list_data):
　　 if len(num_list) == 1:
　　 return list_data[0]
　　 else:
　　 return list_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：

def towersOfHanoi(number, source=1, destination=3, auxiliary=2):
　　 if number >= 1:
　　 towersOfHanoi (number - 1, source, auxiliary, destination)
　　 print("Move disk %d from tower %d to tower %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数据结构之递归方法详解的详细内容，更多关于Python 数据结构递归的资料请关注盛行IT软件开发工作室其它相关文章！

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