Python中这段互递归奇偶判断代码为何及如何生效？

问题说明 #

这段用于判断奇偶性的Python互递归代码运行结果符合预期，但存在疑问：调用is_odd函数时，数值最终会递减到0，此时is_even返回True，按直觉is_odd应返回False，但实际代码能正确判断奇偶，需要理解其工作原理及正确性原因。

代码示例 #

#!/bin/python

def is_even(x):
  if x == 0:
    return True
  else:
    return is_odd(x-1)

def is_odd(x):
  return not is_even(x)


print(is_odd(2))
print(is_even(2))
print(is_odd(3))
print(is_even(3))

运行输出 #

False
True
True
False

工作原理与正确性解释 #

我们通过拆解具体调用过程来理解：

1. 调用is_odd(2)的完整流程 #

• is_odd(2) → 返回 not is_even(2)
• is_even(2) → 2≠0，返回 is_odd(1)
• is_odd(1) → 返回 not is_even(1)
• is_even(1) → 1≠0，返回 is_odd(0)
• is_odd(0) → 返回 not is_even(0)
• is_even(0) → 触发基准条件，返回True
• 反向回溯结果：
  • is_odd(0) = not True → False
  • is_even(1) = False
  • is_odd(1) = not False → True
  • is_even(2) = True
  • is_odd(2) = not True → False（与输出一致）

2. 调用is_odd(3)的完整流程 #

• is_odd(3) → 返回 not is_even(3)
• is_even(3) → 返回 is_odd(2)（已得出结果为False）
• is_even(3) = False
• is_odd(3) = not False → True（与输出一致）

核心逻辑 #

• 基准条件是**is_even(0)=True**，这是数学定义：0是偶数。
• 互递归的本质是利用奇偶性的互补关系推导：
  • 若x≠0，x是偶数等价于x-1是奇数（is_even(x) = is_odd(x-1)）
  • x是奇数等价于x不是偶数（is_odd(x) = not is_even(x)）
• 你之前的误解是只关注到最终is_even(0)=True，但忽略了递归过程中not操作的层级：每一层is_odd都会对下一层的is_even结果取反，递归层数等于输入数值的大小，取反次数刚好匹配奇偶性判断——偶数次取反后结果与基准值一致，奇数次取反后结果与基准值相反，最终刚好对应输入数值的奇偶性。

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