Python多递归调用执行逻辑解析及示例函数分步说明

一、递归调用的工作机制 #

Python中的递归是深度优先执行的：当函数里存在多个递归调用时，会先完整执行第一个递归调用（即深入到该递归的最底层，直到触发终止条件返回结果），再继续执行后续代码（包括第二个递归调用）。

简单来说，就是先把第一个递归的所有嵌套调用都跑完拿到结果，才会轮到第二个递归启动执行，不会在第一个递归执行中途跳去跑第二个递归。

二、代码逻辑与输出结果解析 #

函数核心逻辑 #

这个encodings函数的作用是生成数字字符串的所有有效拆分方式（拆分出的每个数字需≤26），最终用逗号拼接成字符串：

• 终止条件：当输入的str为空时，返回当前已拼接好的prefix组成的列表（递归到此结束）。
• 当str不为空时：
  1. 先处理单个字符拆分：递归调用函数处理去掉第一个字符后的子串，同时把当前字符拼接到prefix后（已有内容时加逗号分隔），将返回的结果加入总结果列表。
  2. 再判断前两个字符是否能组成有效数字（≤26）：如果满足，就递归调用函数处理去掉前两个字符后的子串，把这两个字符拼接到prefix后，将返回的结果也加入总结果列表。

针对输入"1234"的执行过程 #

我们一步步拆解encodings("1234")的执行流程：

1. 初始调用：encodings("1234", "")
   • 先执行第一个递归：encodings("234", "1")
     • 进入encodings("234", "1")后，先执行第一个递归：encodings("34", "1,2")
       • 进入encodings("34", "1,2")后，先执行第一个递归：encodings("4", "1,2,3")
         • 进入encodings("4", "1,2,3")后，执行递归encodings("", "1,2,3,4")，触发终止条件，返回["1,2,3,4"]
         • 此时str长度为1，不满足第二个递归的条件，所以encodings("4", "1,2,3")返回["1,2,3,4"]
       • 回到encodings("34", "1,2")，前两个字符"34"转成整数是34>26，不触发第二个递归，返回["1,2,3,4"]
     • 回到encodings("234", "1")，前两个字符"23"≤26，触发第二个递归：encodings("4", "1,23")
       • 进入encodings("4", "1,23")后，执行递归encodings("", "1,23,4")，返回["1,23,4"]，无第二个递归，所以返回该列表
     • 此时encodings("234", "1")的结果列表是["1,2,3,4"] + ["1,23,4"] = ["1,2,3,4", "1,23,4"]
   • 回到初始调用，前两个字符"12"≤26，触发第二个递归：encodings("34", "12")
     • 进入encodings("34", "12")后，先执行第一个递归：encodings("4", "12,3")
       • 执行递归encodings("", "12,3,4")，返回["12,3,4"]，无第二个递归，所以返回该列表
     • 前两个字符"34">26，不触发第二个递归，所以encodings("34", "12")返回["12,3,4"]
   • 初始调用的结果列表是["1,2,3,4", "1,23,4"] + ["12,3,4"]，也就是最终输出的列表。

最终输出结果 #

['1,2,3,4', '1,23,4', '12,3,4']

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