CODEWITHSUNDEEP
pythonpython-3.x
Phillip England
Phillip England

Reputation: 41

Python - Hard time understanding this recursion code example

I am trying to understand how this piece of code works. It is basic recursion, but I am having a hard time grasping the concept.

The code comes from the sololearn app and I have read their tutorials on the topic but have failed to understand the concept. You will get a boolean value every time you print out the return value of the functions, but I dont understand how the functions are getting to that results. Like I can run the code and see the output, but I need to know HOW it works. Love ya!!

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

Upvotes: 0

Views: 344

Answers (3)

RockAndRoleCoder
RockAndRoleCoder

Reputation: 320

So lets just break this down by steps. 

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.

Here's a breakdown -> 

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

Upvotes: 0

pygeek
pygeek

Reputation: 7404

I've added some useful print statements, hopefully this helps to understand what's actually being executed when is_odd is invoked:

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

print(is_odd(2))

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

Also, consider using python debugger to interactively inspect your code as it's running.

References

Python Debugger: https://docs.python.org/3/library/pdb.html

Upvotes: 0

moonGoose
moonGoose

Reputation: 1510

Try tracing the execution, the left-hand-side of a (=>) indicates a new call to one of the functions, the right-hand-sides indicate what steps are taken to determine the end result.

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

Or this might help more,

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

FWIW, these functions are what's called "mutually recursive" (ie. more than 1 function calling into each other). If you're not comfortable with recursion, you should probably start with a simple single recursion, common examples would be fibonnaci numbers or factorial function.

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)

Upvotes: 1

Related Questions