如何用Python打印斐波那契递归调用树的层级展开日志

该需求完全可以实现。

原有代码出错的核心原因有两个：

• 采用深度优先（DFS）的递归遍历逻辑，会先遍历完整条左子树再处理右子树，输出顺序不符合从上到下的层级输出要求
• 字符串模板拼接逻辑错误：每次替换占位符时错误填入了当前节点的n值，导致输出出现重复的fib(n)内容

我们可以改用广度优先（BFS）的遍历逻辑，按层级展开递归节点，每展开完一层就输出一次完整的表达式，刚好匹配你需要的输出效果。修正后代码如下：

from loguru import logger
from collections import deque

def fibonacci(n):
    """
    基于BFS按层级输出递归树的斐波那契实现
    """
    # 初始化第一层表达式并输出
    level_expr = f"fib({n})"
    logger.debug(level_expr)
    # BFS队列元素格式：(当前节点的n值, 节点在表达式中的起始索引, 所属层级)
    queue = deque([(n, 0, 1)])
    
    current_level = 1
    next_level_expr = level_expr

    while queue:
        curr_n, start_idx, level = queue.popleft()
        # 层级切换时打印上一层完整表达式
        if level > current_level:
            logger.debug(next_level_expr)
            current_level = level
        # 1、2阶斐波那契为叶子节点，无需展开
        if curr_n <= 2:
            continue
        
        # 替换当前节点为两个子节点的表达式
        old_node = f"fib({curr_n})"
        new_node = f"(fib({curr_n-1}) + fib({curr_n-2}))"
        next_level_expr = next_level_expr[:start_idx] + new_node + next_level_expr[start_idx+len(old_node):]

        # 计算两个子节点在新表达式中的索引，加入下一层队列
        left_start = start_idx + 1
        queue.append((curr_n-1, left_start, level+1))
        right_start = start_idx + len(f"(fib({curr_n-1}) + ")
        queue.append((curr_n-2, right_start, level+1))
    
    # 递归计算斐波那契数值，可按需和上层遍历逻辑合并
    def calc(x):
        if x <= 0:
            return 0
        elif x in (1,2):
            return 1
        return calc(x-1) + calc(x-2)
    return calc(n)

# 测试调用
if __name__ == "__main__":
    result = fibonacci(5)
    logger.debug(f"计算结果：{result}")

运行上述代码调用fibonacci(5)的输出如下，完全符合预期：

fib(5)
(fib(4) + fib(3))
((fib(3) + fib(2)) + (fib(2) + fib(1)))
(((fib(2) + fib(1)) + fib(2)) + (fib(2) + fib(1)))

如果不需要外层括号，只需把替换节点的new_node变量去掉外层括号即可。

内容的提问来源于stack exchange，提问作者user6308605