Попробуйте отследить выполнение, левая часть (=>) указывает на новый вызов одной из функций, правая часть указывает, какие шаги предпринимаются для определения конечного результата.

is_odd(1) => not is_even(1)
    is_even(1) => is_odd(0)
        is_odd(0) => not (is_even(0))
            is_even(0) => True
                  => not (True)
                  => False
               => False
          => not (False)
          => True

Или это могло бы помочь больше,

is_odd(1)
=> not is_even(1)
=> not (is_odd(0)
=> not (not (is_even(0))
=> not (not (True))
=> not (False)
=> True

FWIW, эти функции являются так называемыми «взаимно рекурсивными» (то есть более чем одна функция вызывает друг друга). Если вас не устраивает рекурсия, вам, вероятно, следует начать с простой единственной рекурсии, распространенными примерами которой являются числа Фибоначчи или факториальная функция.

def fact(n):
    if n == 0: 
        return 1
    else: 
        return n * fact (n-1)

def fib(n): 
    if n == 0: 
        return 1
    elif n == 1: 
        return 1
    else:
        return fib (n-1) + fib (n-2)

Я добавил несколько полезных операторов печати, надеюсь, это поможет понять, что на самом деле выполняется при вызове is_odd:

def is_even(x):
    if x == 0:
        print("return True")
        return True
    else:
        print("return is_odd({0}-1)".format(x))
        return is_odd(x-1)

def is_odd(x):
    print("return not is_even({0})".format(x))
    return not is_even(x)

print(is_odd(1))

return not is_even(1)
return is_odd(1-1)
return not is_even(0)
return True
True

[ 115]

return not is_even(2)
return is_odd(2-1)
return not is_even(1)
return is_odd(1-1)
return not is_even(0)
return True
False

Также рассмотрите возможность использования python-отладчика для интерактивной проверки вашего кода во время его работы.

Ссылки

Отладчик Python: https://docs.python.org/3/library/pdb.html

Итак, давайте разберем это по шагам.

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(1))

1) we say print -> is_odd(1).  So we're sending a 1 to is_odd() function
2) is_odd() recieves the 1 and before it can return a value, it must call is_even() and send that same 1.
3) is_even() now recieves that 1 and checks if its equal to zero, but it fails, so it then has to call is_odd() and send it 1 - 1.  
4) is_odd checks the new value (zero in this case) and calls again is_even() sending that zero
5) is_even() now resovles at the if x == 0: line and returns True.  
6) Now we've reached the end of the recursive loop and all the functions will resolve with their return statments.  Starting with the is_even() being True.  

Вот разбивка ->

print(is_odd(1)) -> 
    print(NOT is_even(1))->
       print(NOT is_odd(1-1)) ->
         print(NOT NOT is_even(0)) -> 
           print(is_even(0)) -> 
               print(True) ->
                 True