递归子程序是一种在函数或过程中调用自身的方法，通常用于解决可以分解为更小子问题的问题。以下是编写递归子程序的一般步骤和示例：
确定基准情况（Base Case）：
这是递归的终止条件，防止无限递归。
确定递归步骤（Recursive Case）：
这是将原问题转化为规模更小的子问题的过程。
示例1：计算阶乘
阶乘是一个经典的递归问题。以下是一个用Python编写的计算阶乘的递归子程序：
```python
def factorial（n）:
基准情况
if n == 0:
return 1
递归步骤
else:
return n * factorial（n - 1）
测试
result = factorial（5）
print（f"5的阶乘是： {result}"） 输出： 5的阶乘是： 120
```
示例2：斐波那契数列
斐波那契数列是另一个经典的递归问题。以下是一个用Python编写的计算斐波那契数列的递归子程序：
```python
def fibonacci（n）:
基准情况
if n == 0:
return 0
elif n == 1:
return 1
递归步骤
else:
return fibonacci（n - 1） + fibonacci（n - 2）
测试
print（fibonacci（10）） 输出： 55
```
示例3：汉诺塔问题
汉诺塔问题是一个经典的递归问题。以下是一个用Python编写的解决汉诺塔问题的递归子程序：
```python
def hanoi（n, source, target, auxiliary）:
if n > 0:
将前n-1个盘子从source移到auxiliary
hanoi（n - 1, source, auxiliary, target）
将第n个盘子从source移到target
print（f"Move disk {n} from {source} to {target}"）
将前n-1个盘子从auxiliary移到target
hanoi（n - 1, auxiliary, target, source）
测试
hanoi（3, 'A', 'C', 'B'）
```
示例4：树的遍历
```python
class TreeNode:
def __init__（self, value）:
self.value = value
self.left = None
self.right = None
def inorder_traversal（root）:
if root:
递归遍历左子树
inorder_traversal（root.left）
访问根节点
print（root.value）
递归遍历右子树
inorder_traversal（root.right）
构建一个简单的二叉树
1
/ \
2 3
/ \
4 5
root = TreeNode（1）
root.left = TreeNode（2）
root.right = TreeNode（3）
root.left.left = TreeNode（4）
root.left.right = TreeNode（5）
执行中序遍历
inorder_traversal（root）
```
总结
编写递归子程序的关键在于明确基准情况和递归步骤。基准情况是递归的终止条件，递归步骤是将问题分解为更小的子问题。通过这两个步骤，可以逐步缩小问题的规模，直到达到基准情况为止。在实际应用中，递归子程序广泛应用于各种算法和数据结构中，如排序、搜索、树遍历等。