python——递归函数

python递归的经典案例

随着计算机科学的发展，递归在编程语言中成为一种非常重要的编程技术。Python作为一种高级编程语言，具有很好的递归支持，它常常被用于解决一些复杂的问题。在本文中，我们将介绍Python递归的经典案例，希望能为读者们提供一些有用的编程知识。

1. 杨辉三角

杨辉三角是一个典型的递归问题。它是由数学家杨辉在13世纪发现的，它可以用来求解组合数学问题。在Python中，实现这个问题可以使用递归函数。

def generate(numRows):

if numRows == 0:

return []

elif numRows == 1:

return [[1]]

else:

result = generate(numRows-1)

last_row = result[-1]

new_row = [1]

for i in range(1, numRows-1):

new_row.append(last_row[i-1] + last_row[i])

new_row.append(1)

result.append(new_row) return result

2. 斐波那契数列

斐波那契数列是计算机科学中的一个经典问题之一。它是一个具有递归结构的数列，即前两个数之和等于第三个数。在Python中，求解斐波那契数列可以使用递归函数。

def fibonacci(n):

if n == 0:

return 0

elif n == 1:

return 1

else:

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

Python之递归函数

在函数内部，可以调用其他函数。如果一个函数在内部调用自身本身，这个函数就是递归函数。

举个例子，我们来计算阶乘 n! = 1 * 2 * 3 * ... * n，用函数 fact(n)表示，可以看出：

fact(n) = n! = 1 * 2 * 3 * ... * (n-1) * n = (n-1)! * n = fact(n-1) * n

所以，fact(n)可以表示为 n * fact(n-1)，只有n=1时需要特殊处理。

于是，fact(n)用递归的方式写出来就是：

def fact(n):

if n==1:

return 1

return n * fact(n - 1)

上面就是一个递归函数。可以试试：

>>>fact(1)

1

>>>fact(5)

120

>>>fact(100)

93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000L

如果我们计算fact(5)，可以根据函数定义看到计算过程如下：

===>fact(5)

===> 5 * fact(4)

===> 5 * (4 * fact(3))

===> 5 * (4 * (3 * fact(2)))

===> 5 * (4 * (3 * (2 * fact(1))))

===> 5 * (4 * (3 * (2 * 1)))

===> 5 * (4 * (3 * 2))

===> 5 * (4 * 6)

===> 5 * 24

===> 120 递归函数的优点是定义简单，逻辑清晰。理论上，所有的递归函数都可以写成循环的方式，但循环的逻辑不如递归清晰。

- 1 - python 递归调用

Python递归调用是一种函数调用自身的方法。递归函数和普通函数的区别在于，递归函数可以直接或间接地调用自身，而普通函数不可以。在Python中，递归函数通常用于解决需要重复执行相同操作的问题。

递归函数必须包含一个终止条件，否则它将陷入无限循环。当递归函数满足终止条件时，它将返回值并逐级回溯到调用函数。

递归函数在处理复杂问题时非常有用。例如，计算斐波那契数列可以使用递归函数。斐波那契数列是一个数列，其中每个数字都是前两个数字的和，从0和1开始。因此，数列的前几个数字是0，1，1，2，3，5，8，13等。

以下是一个计算斐波那契数列的递归函数示例：

```

def fibonacci(n):

if n <= 1:

return n

else:

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

```

在上面的函数中，如果n小于或等于1，则函数返回n。否则，函数将继续递归调用自身，并返回前两个斐波那契数列数字的总和。

python利⽤递归函数输出嵌套列表的每个元素

1.先⽤ for 循环取。

for item in l:

if isinstance(item ,list):

for newitem in item:

print(newitem)

else:

print(item

输出：1

2

3

4

5

6

#利⽤ for 循环取值，有⼏层嵌套就要写⼏层 for 循环，否则不识别。

l=[1,2,[3,4],[5,6,[7,8]]]

for item in l:

if isinstance(item ,list):

for newitem in item:

print(newitem)

else:

print(item

输出：1

2

3

4

5

6

[7, 8]

2.递归函数实现：

递归函数实现：def getitem(l):

for item in l:

if isinstance(item,list):

getitem(item)

else:

print(item)

getitem(l)

输出:1

2

3

4

5

6

7

8

9

10

变式1：遇到类表就缩进⼀次：

def getitem(l,level=0):

for item in l:

if isinstance(item,list):

getitem(item,level+1)

else:

for tab in range(level):

print('\t',end='' #输出⼀个 制表符，并且将 print 后⾯的换⾏符去掉，这样就是了缩进

print(item)

getitem(l)

输出：

变式2：加⼊开启机制，是否缩进def getitem(l,level=0,count=False):

for item in l:

if isinstance(item,list):

getitem(item,level+1,count)

else:

if count:

for tab in range(level):