I've tried to understand for about 2 hours, but I'm still confused.

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

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

CodePudding user response：

In recursion, you keep on looping through the same operation until a condition breaks that loop. Let's go through your code with an example.

Is 1 odd or even?

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

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

print(is_even(1))

In this example,

• def is_even(n) is called. n = 1
• n is not 0, so the else condition is reached
• Return is_odd(0) is called but we don't know what is_odd is
• (A) So, is_odd(0) is called before the return can happen
• ..(B) is_odd returns the inverse of is_even(0), but we have to find out what is_even(0) is
• .... is_even(0) checks whether n = 0. It is. So, it returns True
• ..(B) gets True. It returns the inverse of True, which is False. (B) returns False
• (A) receives False and returns it to print
• print prints False

Now try to follow the same logic with 2. You'll undergo more steps than above.

CodePudding user response：

For a recursive function to be successful (not recurse infinitely), it needs two things:

1. A recursive function must always have a base case (or exit condition)
2. A recursive function must tend towards the base case (or in other words, it must reduce the "size" of the problem to a smaller version of the same problem iteratively until the base case is reached)

The base case for this function is when n == 0 at which point the is_even() function returns a value, True, as opposed to returning the result of a function call.

What is_even() does is call itself with ever decreasing values of n until n == 0 at which point it returns True because it has reached the base case. The reason it works is because each recursive call tacks on a boolean not to its return value.

A call to this function will therefore return either an even number of negations in front of a True or an odd number of negations. If there are an even number of negations, then each pair will cancel out and you'll end up with True. If there are an odd number of negations, then you'll end up with one last not in front of a True.

Examples:

is_even(2) = not is_even(1)
           = not (not is_even(0))  # base case, returns True
           = not (not True)
           = not (False)
           = True

is_even(3) = not is_even(2)
           = not (not is_even(1))
           = not (not (not is_even(0)))  # base case, returns True
           = not (not (not True))
           = not (not (False))
           = not (True)
           = False

Note that the way your code is written, it's possible to recurse infinitely by initially calling is_even() with any negative integer (or any non-integral float). This will raise a RecursionError.

This is because even though is_even() satisfies the first rule (must have a base case), it violates the second rule in some cases (it doesn't always reduce the problem to a "smaller version of itself". In this case, by calling is_even(-1), each recursive call will subtract 1 from this value, thereby growing the size of the problem:

is_even(-1) = not is_even(-2)
            = not (not is_even(-3))
            = not (not (not is_even(-4)))
            .
            .
            .

Same thing happens with a non-integral float:

is_even(1.1) = not is_even(0.1)
             = not (not is_even(-0.9))
             = not (not (not is_even(-1.9)))
             .
             .
             .