递归中子函数与父函数的关联及回溯组合中i的追踪问题

问题背景 #

这是我的第一个技术问题，若格式存在疏漏敬请谅解。近期我在学习递归与回溯问题，虽理解基础逻辑，但难以可视化调用栈。我遇到的问题是：输入一个数字，找出所有相加等于该数的正整数组合，示例输入输出及实现代码如下：

示例输入输出 #

input:
5
output:
1 1 1 1 1
1 1 1 2
1 1 3
1 2 2
1 4
2 3
5

实现代码 #

def find_combinations(magical_number):
    def find_combinations_recursively(remaining, start, combination):
        if remaining == 0:
            # Print the combination
            print(" ".join(map(str, combination)))
            return

        for i in range(start, remaining + 1):
            combination.append(i)
            # Recursively find combinations
            find_combinations_recursively(remaining - i, i, combination)
            combination.pop()

    combination = []
    find_combinations_recursively(magical_number, 1, combination)

我的疑问与尝试 #

我的疑问是：变量i如何随递归调用递增？递归展开时该如何追踪i的变化？我尝试用纸笔可视化调用栈（以数字3为例）但仍有困惑，如下是我的可视化过程：

1. Initial Call:
   - find_combinations_recursively(3, 1, [])
     - Stack: [remaining=3, start=1, i=None, Parent=None]

2. First Iteration (i=1):
   - find_combinations_recursively(2, 1, [1])
     - Stack: [remaining=2, start=1, i=1, Parent=(3, 1, None)]
       - find_combinations_recursively(1, 1, [1, 1])
         - Stack: [remaining=1, start=1, i=1, Parent=(2, 1, 1)]
           - find_combinations_recursively(0, 1, [1, 1, 1])
             - Stack: [remaining=0, start=1, i=1, Parent=(1, 1, 1)]

   - find_combinations_recursively(0, 2, [1, 2])
     - Stack: [remaining=0, start=2, i=2, Parent=(2, 1, 1)]

3. Second Iteration (i=2):
   - find_combinations_recursively(2, 2, [2])
     - Stack: [remaining=2, start=2, i=2, Parent=(3, 1, None)]
       - find_combinations_recursively(0, 2, [2, 2])
         - Stack: [remaining=0, start=2, i=2, Parent=(2, 2, 2)]

4. Third Iteration (i=3):
   - find_combinations_recursively(3, 3, [3])
     - Stack: [remaining=3, start=3, i=3, Parent=(3, 1, None)]
       - find_combinations_recursively(0, 3, [3, 3])
         - Stack: [remaining=0, start=3, i=3, Parent=(3, 3, 3)]

请问我的可视化方式是否有误？采用树结构是否更合适？

解答 #

你的可视化过程中的错误 #

1. 剩余值计算错误：

   • 当进入i=3的迭代时，remaining是3，调用递归时应该是remaining - i = 3-3=0，正确调用为find_combinations_recursively(0, 3, [3])，而非(3, 3, [3])；后续[3,3]组合总和为6，明显超过3，属于错误记录，此时combination应为[3]，满足条件直接输出。
   • 同理，i=2的迭代中，remaining=2，调用递归时remaining-i=0，正确组合是[2]，而非[2,2]，[2,2]总和为4不符合要求，该递归调用会直接触发remaining==0的条件，输出[2]。

2. 调用栈的i值记录混淆：
   栈中的i应是当前循环中正在处理的数值，而非递归调用传入的start。比如find_combinations_recursively(2,1,[1])的循环中，i从1开始，处理完i=1的递归后，才会回到循环处理i=2，这部分你记录正确，但后续错误组合需修正。

变量i的变化逻辑 #

i的递增与递归的核心关联是递归调用时传入的start参数为当前的i：

• 每一层递归的for循环从start开始遍历，保证后续添加的数字不会小于当前数字，避免生成重复组合（比如不会同时出现1+2和2+1）。
• 递归返回后，会回到当前循环的下一个i继续执行，比如在remaining=2, start=1的循环中，先处理i=1的递归，完成后回到循环处理i=2，这就是i递增的过程。

树结构可视化更合适 #

是的，树结构能更清晰展示递归展开过程：

• 每个节点代表一次递归调用，包含remaining、start、当前combination三个属性。
• 每个节点的子节点对应for循环中不同i的递归调用。

以数字3为例，树结构如下：

根节点: (remaining=3, start=1, [])
├─ i=1 → 子节点: (remaining=2, start=1, [1])
│  ├─ i=1 → 子节点: (remaining=1, start=1, [1,1])
│  │  └─ i=1 → 子节点: (remaining=0, start=1, [1,1,1]) → 输出
│  └─ i=2 → 子节点: (remaining=0, start=2, [1,2]) → 输出
├─ i=2 → 子节点: (remaining=1, start=2, [2]) → 循环i从2开始，2>1，无后续调用，无输出
└─ i=3 → 子节点: (remaining=0, start=3, [3]) → 输出

这样能直观看到每一步的i选择和递归走向，也能清楚哪些路径会生成有效组合。

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