递归检查奇数或偶数

Question

在这段代码中:

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_even(2))
print(is_odd(2))

我一直在脑子里想着这个,并想知道它是如何工作的.在我看来,最终x在is_even(x)将返回True每次.但是,当我运行代码时,它工作得非常好,True并且False适当地返回.有人能解释一下这是怎么回事吗？

我理解递归的基本概念,并完全理解着名的因子示例是如何工作的.然而,这个对我来说很难缠头.

现在感到无能为力......

Answer 1

在找到基本情况之前,总是有助于分解递归关系.

is_even(2) => return is_odd(1) 
           => return not is_even(1) 
           => return not is_odd(0)
           => return not not is_even(0)
           => return not not True
           => return True            ---- (1)

is_odd(2) => return not is_even(2) 
          => return not True       [from (1)] 
          => return False

一般来说,从你的递归函数中,很容易观察到is_even(n)会返回[not not not ... n times] True,同时is_odd(n)会返回[not not not ... n - 1 times] True.所以nots 的数量和最终的表达式取决于n(aha!).那么,这肯定是一种迂回的方式来询问是否

n % 2 == 0

Answer 2

添加几个print语句,您将看到它正在做什么:

from __future__ import print_function

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

def is_odd(x):
    print('not', end=' ')
    return not is_even(x)

>>> is_even(5)
not not not not not True
False
>>> is_odd(5)
not not not not not not True
True