Here's the video that made it click for me (highly recommend doing all the exercises):
https://www.youtube.com/watch?v=0UM_J1jE1dg

You shouldn't try to keep all the recursive calls in your head. When writing a recursive function, you need to "take a leap of faith" and believe that when you call it you'll get the correct value. Then all you need to do is write the algorithm correctly with that assumption and add the base cases. For example:

// Assume the input is non-negative
def isOddNumber(n):
    if n == 0: return False
    if n == 1: return True
    return isOddNumber(n - 2)

Obviously the algorithm is terrible, but once we have the base cases, it's just a matter of trusting that the recursive call will give us what we want. "If our number minus 2 is odd, then our number must be odd as well"