2024年6月2日发(作者：)
递归函数简单实例
递归函数是一种自我调用的函数，它在运行过程中会重复调用自身，
直到满足一定条件时停止。递归函数一般由两部分组成：基准情形和递归
情形。基准情形指的是当满足一定条件时停止递归，递归情形指的是当不
满足基准情形时继续进行递归调用。
下面我将介绍几个简单的递归函数实例。
1.计算阶乘
阶乘是指自然数n乘以比它小的所有自然数的乘积。使用递归函数可
以很方便地计算阶乘。
```python
def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n-1)
```
在上面的递归函数中，基准情形是当n等于0时，返回1；递归情形
是当n大于0时，返回n与factorial(n-1)的乘积。函数会一直递归调
用自身，直到n等于0。
2.斐波那契数列
斐波那契数列是指前两个数为1，从第三个数开始，每个数都是前两
个数的和。
```python
def fibonacci(n):
if n <= 0:
return 0
elif n == 1 or n == 2:
return 1
else:
return fibonacci(n-1) + fibonacci(n-2)
```
在上面的递归函数中，基准情形是当n小于等于0时，返回0；当n
等于1或2时，返回1；递归情形是当n大于2时，返回fibonacci(n-1)
与fibonacci(n-2)的和。函数会一直递归调用自身，直到n小于等于2
3.迷宫问题
假设有一个n×n的迷宫，每个位置可以是空地(用0表示)或是墙壁
(用1表示)。求从(0,0)位置到(n-1,n-1)位置的路径。
```python
def find_path(maze, x, y, path):
n = len(maze)
if x == n-1 and y == n-1:
return True
elif x >= 0 and x < n and y >= 0 and y < n and maze[x][y] ==
0:
((x, y))
maze[x][y] = 2
if find_path(maze, x+1, y, path) or find_path(maze, x, y+1,
path):
return True
return False
```
在上面的递归函数中，基准情形是当x和y分别等于n-1时，表示已
经到达目标位置，返回True；递归情形是当当前位置为可行走的空地时，
尝试向下和向右移动，如果有一条路径能够到达目标位置，返回True；
如果当前位置不是可行走的空地，或者两条路径均不能到达目标位置，将
当前位置从路径中去除，返回False。函数会一直递归调用自身，尝试不
同的路径。
这些是递归函数的简单实例，递归函数可以解决许多复杂的问题。但
需要注意的是，在使用递归函数时，一定要注意设置好基准情形，避免造
成无限循环。
发布评论