关于递归函数基例的说明

递归函数在Python中是一种常见的编程技巧，其基本思想是函数调用自身来解决问题。这里以经典的阶乘计算为例[^1]：

def tail_recursive_fact(n, acc=1):
    """
    使用尾递归优化的阶乘函数
    :param n: 非负整数
    :param acc: 计算结果的累积器（初始值设为1）
    :return: n的阶乘
    """
    if n == 0 or n == 1:
        return acc
    else:
        return tail_recursive_fact(n - 1, n * acc)

# 示例
print(tail_recursive_fact(5))  # 输出：120

在这个`tail_recursive_fact`函数中，我们通过传递当前的累积值`acc`和减小的`n`，避免了直接的乘法运算，使得每次递归调用都是对上一次调用的结果进行累加，从而实现了尾递归。

尽管递归函数简洁直观，但并非所有的递归都能轻易转换为循环，因为递归的优势在于其能够自然地表示分治策略。然而，对于深度过大的递归，如果不采用尾递归优化，可能会导致栈溢出问题。因此，理解何时使用递归以及如何优化递归实现至关重要。

相关问题

p4913 【深基16.例3】二叉树深度

### 回答1：
题目描述：

给定一棵二叉树，求其深度。

输入格式：

第一行包含一个整数 n，表示二叉树的节点个数。

接下来 n 行，每行包含三个整数 fa, lch, rch，表示节点的父节点编号，左儿子编号和右儿子编号。根节点的父节点编号为 0，如果某个节点不存在左儿子或右儿子，则对应的编号为 −1。

输出格式：

输出一个整数，表示二叉树的深度。

数据范围：

1≤n≤1000

输入样例：

5
0 1 2
1 3 -1
2 -1 4
3 -1 -1
4 -1 -1

输出样例：

3

解题思路：

递归求解二叉树深度，每次递归时，将左右子树的深度取最大值加一即可。

C++ 代码

### 回答2：
题目：p4913 【深基16.例3】二叉树深度。

【题目描述】
给定一棵二叉树，求其深度。
【输入格式】
第一行包含一个整数n，表示二叉树的节点个数。
接下来n行，每行包含三个整数，表示一个节点及其左右子节点的编号，其中-1表示该节点为空。
【输出格式】
输出一个整数，表示二叉树的深度。

【示例输入】
6
1 2 3
2 4 5
3 -1 6
4 -1 -1
5 -1 -1
6 -1 -1

【示例输出】
3

【解题思路】
采取递归的方式求解二叉树的深度。对于一个二叉树来说，它的深度等于其左子树深度和右子树深度的较大值加1。
【代码实现】

def tree_depth(root, depth):
    if root == -1:  # 如果节点为空，返回深度
        return depth
    else:
        left_depth = tree_depth(nodes[root][0], depth + 1)  # 左子树深度
        right_depth = tree_depth(nodes[root][1], depth + 1)  # 右子树深度
        return max(left_depth, right_depth)  # 返回左右子树深度的较大值

n = int(input())  # 节点个数
nodes = {}  # 节点字典
for i in range(n):
    nodes[i + 1] = list(map(int, input().split()))

depth = tree_depth(1, 0)  # 从根节点开始求解深度，初始化深度为0
print(depth)

【代码说明】
首先定义一个递归函数tree_depth，传入两个参数：root表示当前节点的编号，depth表示当前节点的深度。
如果当前节点为空，即root为-1，表示到达叶子节点，返回深度depth。
如果当前节点不为空，分别求解左子树和右子树的深度，即left_depth和right_depth。
最后返回左右子树深度的较大值，即max(left_depth, right_depth)。
读入节点个数n，并创建一个字典nodes，用于存储节点及其左右子节点的编号。
接下来，使用循环读入每个节点的信息，并将其存入字典nodes中。
最后调用tree_depth函数，从根节点开始求解深度，初始深度为0，将结果打印出来。