递归函数出现“'int' object is not subscriptable”错误及排序问题

我尝试编写一个递归函数，实现将列表中的所有奇数按升序排列，之后跟随降序排列的偶数。例如：
输入列表lst = [1, 2, 3, 4, 6, 11, 13, 14, 15, 17, 18]，预期返回[1, 3, 11, 13, 15, 17, 18, 14, 6, 4, 2]。

我的代码 #

def REC_fun(lst):
    lst2 , lst3 = [] , []
    
    if len(lst) == 1:
        return lst[0]
    temp = REC_fun(lst[1:])
    if temp[0]%2 == 1:
        lst2 += [temp[0]]
    else:
        lst3 += [temp[0]]
    return lst2 + lst3[::-1]

ls = [1, 2, 3, 6, 11, 13, 14, 15, 17, 18]
REC_fun(ls)

遇到的错误 #

我想每次判断列表首个数字的奇偶性，并将其分别添加到空列表lst2和lst3中，但一直出现如下错误：

~\AppData\Local\Temp/ipykernel_16808/3849482424.py in REC_fun(lst)
      7     if len(lst) == 1:
      8         return lst[0]
----> 9     temp = make_pyramid(lst[1:])
     10     if temp[0]%2 == 1:
     11         lst2 += [temp[0]]

~\AppData\Local\Temp/ipykernel_16808/3849482424.py in REC_fun(lst)
      8         return lst[0]
      9     temp = make_pyramid(lst[1:])
---> 10     if temp[0]%2 == 1:
     11         lst2 += [temp[0]]
     12     else:

TypeError: 'int' object is not subscriptable

编辑尝试 #

我将首次返回值从return lst[0]改为return lst后，输出结果变为[18]。

问题分析与解决方案 #

核心问题 #

1. 返回值类型不一致：原代码中，列表长度为1时返回整数lst[0]，但后续递归调用却把返回值当成列表去取temp[0]，直接触发类型错误。
2. 递归逻辑错误：没有处理当前列表的第一个元素，反而错误地操作递归返回结果的第一个元素，完全偏离了“逐个分类元素并维护顺序”的目标。
3. 分类后顺序维护缺失：即使分类正确，也没有逻辑保证奇数升序、偶数降序。

修正后的递归代码（通用版，支持任意输入顺序） #

递归的核心逻辑应该是：每次处理当前列表的第一个元素，递归处理剩余部分得到已分类的结果，再将当前元素插入到对应分类的正确位置以维持要求的顺序。

def REC_fun(lst):
    # 基线条件：空列表返回两个空分类列表
    if not lst:
        return [], []
    
    # 递归处理剩余元素，得到升序的奇数列表和降序的偶数列表
    odd_sorted, even_sorted = REC_fun(lst[1:])
    current = lst[0]
    
    if current % 2 == 1:
        # 将奇数插入到升序列表的对应位置
        insert_idx = 0
        while insert_idx < len(odd_sorted) and odd_sorted[insert_idx] < current:
            insert_idx += 1
        odd_sorted.insert(insert_idx, current)
    else:
        # 将偶数插入到降序列表的对应位置
        insert_idx = 0
        while insert_idx < len(even_sorted) and even_sorted[insert_idx] > current:
            insert_idx += 1
        even_sorted.insert(insert_idx, current)
    
    return odd_sorted, even_sorted

# 调用并合并结果
ls = [1, 2, 3, 6, 11, 13, 14, 15, 17, 18]
odds, evens = REC_fun(ls)
print(odds + evens)  # 输出: [1, 3, 11, 13, 15, 17, 18, 14, 6, 2]

简化版（适用于输入列表奇数原本升序、偶数原本升序的场景） #

如果你的输入列表中奇数本身是按升序出现，偶数按升序出现（如示例输入），可以简化递归逻辑：

def REC_fun(lst):
    # 基线条件：空列表直接返回
    if not lst:
        return []
    
    # 递归处理剩余元素
    processed_rest = REC_fun(lst[1:])
    current = lst[0]
    
    if current % 2 == 1:
        # 奇数放在已处理结果的奇数区域最前面（保证升序）
        return [current] + [x for x in processed_rest if x % 2 == 1] + [x for x in processed_rest if x % 2 == 0]
    else:
        # 偶数放在已处理结果的偶数区域最后面（保证降序）
        return [x for x in processed_rest if x % 2 == 1] + [x for x in processed_rest if x % 2 == 0] + [current]

ls = [1, 2, 3, 6, 11, 13, 14, 15, 17, 18]
print(REC_fun(ls))  # 输出: [1, 3, 11, 13, 15, 17, 18, 14, 6, 2]

代码说明 #

• 基线条件：当列表为空时终止递归，返回空结果（或空分类列表）。
• 递归处理：先处理列表的剩余部分，得到已经符合要求的子结果。
• 元素插入：
  • 奇数：通过遍历找到合适位置插入，确保整个奇数列表保持升序；简化版中利用输入的顺序特性，直接放在奇数区域开头即可。
  • 偶数：同样找到合适位置插入以维持降序；简化版中追加到偶数区域末尾，利用输入的升序特性自动形成降序。

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