如何用递归实现列表先偶数后奇数排序（仅允许递归与基础列表操作）

你已经用循环实现了目标功能，现在可以按照递归拆解+元素定位的思路完善递归版本，核心是在递归处理剩余列表后，根据当前元素的奇偶性将其插入到结果的对应区域，同时保持原列表的元素相对顺序。

先修正你原有递归代码的问题：

• 终止条件行缺少冒号
• 未处理空列表的边界情况
• 没有对当前元素的奇偶性做判断和位置处理

完整递归实现代码 #

def eto(lst: list[int]) -> list[int]:
    # 终止条件：空列表直接返回
    if not lst:
        return []
    
    first = lst[0]
    # 递归处理剩余子列表，得到已排序的结果
    rest_sorted = eto(lst[1:])
    
    if first % 2 == 0:
        # 偶数：直接放到已排序结果的最前面，保持原顺序
        return [first] + rest_sorted
    else:
        # 奇数：需要插入到已排序结果中所有偶数的后面、奇数的前面
        if not rest_sorted:
            return [first]
        if rest_sorted[0] % 2 == 0:
            # 剩余结果的第一个元素是偶数，递归调整当前奇数的位置
            return [rest_sorted[0]] + eto([first] + rest_sorted[1:])
        else:
            # 剩余结果的第一个元素是奇数，直接放到最前面
            return [first] + rest_sorted

代码逻辑解释 #

1. 终止条件：当输入列表为空时，直接返回空列表，覆盖空输入、递归到末尾等所有边界情况。
2. 递归拆解：每次取列表的第一个元素，递归处理剩下的子列表，得到已经是「先偶数后奇数」的排序结果。
3. 元素定位：
   • 偶数处理：直接拼在递归结果的最前面，保证原列表中先出现的偶数排在更靠前的位置，和循环版本的顺序一致。
   • 奇数处理：检查递归结果的第一个元素，如果是偶数，就把当前奇数和递归结果的剩余部分重新传入递归函数，实现将奇数插入到偶数区域之后；如果递归结果的第一个元素已经是奇数，直接把当前奇数拼在最前面，保持奇数的原顺序。

测试验证 #

用循环版本的测试案例验证：

• 输入 [3,2,1]，递归返回 [2,3,1]，和循环版本结果一致。
• 输入 [1,3,2,4]，递归返回 [2,4,1,3]，符合预期。
• 输入 [2,4,1,3]，递归返回 [2,4,1,3]，正确保留原顺序。

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