Recursively checking for odd or even

In this code:

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

I keep going through this in my head and wondering how it's working. It seems to me that eventually x in is_even(x) will return True every time. However, when I run the code, it works perfectly fine and returns True and False appropriately. Can someone explain how that's happening?

I understand the basic concept of recursion and fully understand how the famous factorial example works. However, this one is hard for me to wrap my head around.

Feeling inept right now...

edited Aug 21 '17 at 17:42

coldspeed

135k23145230

asked Jun 7 '17 at 21:59

Sam Dillard

145112

6

But don't try these approaches on negative numbers ... :)

– MSeifert
Jun 7 '17 at 22:03

3

Trying writing the outputs on a piece of paper

– kiran.koduru
Jun 7 '17 at 22:04

1

If you call is_even(3), one of the recursive calls eventually executed will be is_even(0), but while that recursive call will return True, that's not what is_even(3) will return.

– user2357112
Jun 7 '17 at 22:04

1

@MSeifert just change x to abs(x) everywhere and OP's good to go.

– coldspeed
Jun 7 '17 at 22:04

1

Why do you think is_even will always return True? If you haven't even worked out your thinking enough to actually write it down for us, then it's impossible for us to explain where it went wrong. Which leaves us asking if you even really thought it through. As software developers, we must have the ability to critique our own thinking (or sometimes the lack of our thinking). I'm afraid I must downvote for not doing so. Also, what did the duck say?

– jpmc26
Jun 8 '17 at 0:24

|
show 9 more comments

In this code:

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

I understand the basic concept of recursion and fully understand how the famous factorial example works. However, this one is hard for me to wrap my head around.

Feeling inept right now...

edited Aug 21 '17 at 17:42

coldspeed

135k23145230

asked Jun 7 '17 at 21:59

Sam Dillard

145112

6

But don't try these approaches on negative numbers ... :)

– MSeifert
Jun 7 '17 at 22:03

3

Trying writing the outputs on a piece of paper

– kiran.koduru
Jun 7 '17 at 22:04

1

If you call is_even(3), one of the recursive calls eventually executed will be is_even(0), but while that recursive call will return True, that's not what is_even(3) will return.

– user2357112
Jun 7 '17 at 22:04

1

@MSeifert just change x to abs(x) everywhere and OP's good to go.

– coldspeed
Jun 7 '17 at 22:04

1

Why do you think is_even will always return True? If you haven't even worked out your thinking enough to actually write it down for us, then it's impossible for us to explain where it went wrong. Which leaves us asking if you even really thought it through. As software developers, we must have the ability to critique our own thinking (or sometimes the lack of our thinking). I'm afraid I must downvote for not doing so. Also, what did the duck say?

– jpmc26
Jun 8 '17 at 0:24

|
show 9 more comments

In this code:

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

I understand the basic concept of recursion and fully understand how the famous factorial example works. However, this one is hard for me to wrap my head around.

Feeling inept right now...

edited Aug 21 '17 at 17:42

coldspeed

135k23145230

asked Jun 7 '17 at 21:59

Sam Dillard

145112

In this code:

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

I understand the basic concept of recursion and fully understand how the famous factorial example works. However, this one is hard for me to wrap my head around.

Feeling inept right now...

python recursion

edited Aug 21 '17 at 17:42

coldspeed

135k23145230

asked Jun 7 '17 at 21:59

Sam Dillard

145112

edited Aug 21 '17 at 17:42

coldspeed

135k23145230

asked Jun 7 '17 at 21:59

Sam Dillard

145112

edited Aug 21 '17 at 17:42

coldspeed

135k23145230

edited Aug 21 '17 at 17:42

coldspeed

135k23145230

edited Aug 21 '17 at 17:42

coldspeed

135k23145230

asked Jun 7 '17 at 21:59

Sam Dillard

145112

asked Jun 7 '17 at 21:59

Sam Dillard

145112

asked Jun 7 '17 at 21:59

Sam Dillard

145112

6

But don't try these approaches on negative numbers ... :)

– MSeifert
Jun 7 '17 at 22:03

3

Trying writing the outputs on a piece of paper

– kiran.koduru
Jun 7 '17 at 22:04

1

If you call is_even(3), one of the recursive calls eventually executed will be is_even(0), but while that recursive call will return True, that's not what is_even(3) will return.

– user2357112
Jun 7 '17 at 22:04

1

@MSeifert just change x to abs(x) everywhere and OP's good to go.

– coldspeed
Jun 7 '17 at 22:04

1

Why do you think is_even will always return True? If you haven't even worked out your thinking enough to actually write it down for us, then it's impossible for us to explain where it went wrong. Which leaves us asking if you even really thought it through. As software developers, we must have the ability to critique our own thinking (or sometimes the lack of our thinking). I'm afraid I must downvote for not doing so. Also, what did the duck say?

– jpmc26
Jun 8 '17 at 0:24

|
show 9 more comments

6

But don't try these approaches on negative numbers ... :)

– MSeifert
Jun 7 '17 at 22:03

3

Trying writing the outputs on a piece of paper

– kiran.koduru
Jun 7 '17 at 22:04

1

If you call is_even(3), one of the recursive calls eventually executed will be is_even(0), but while that recursive call will return True, that's not what is_even(3) will return.

– user2357112
Jun 7 '17 at 22:04

1

@MSeifert just change x to abs(x) everywhere and OP's good to go.

– coldspeed
Jun 7 '17 at 22:04

1

Why do you think is_even will always return True? If you haven't even worked out your thinking enough to actually write it down for us, then it's impossible for us to explain where it went wrong. Which leaves us asking if you even really thought it through. As software developers, we must have the ability to critique our own thinking (or sometimes the lack of our thinking). I'm afraid I must downvote for not doing so. Also, what did the duck say?

– jpmc26
Jun 8 '17 at 0:24

But don't try these approaches on negative numbers ... :)

– MSeifert
Jun 7 '17 at 22:03

Trying writing the outputs on a piece of paper

– kiran.koduru
Jun 7 '17 at 22:04

If you call is_even(3), one of the recursive calls eventually executed will be is_even(0), but while that recursive call will return True, that's not what is_even(3) will return.

– user2357112
Jun 7 '17 at 22:04

@MSeifert just change x to abs(x) everywhere and OP's good to go.

– coldspeed
Jun 7 '17 at 22:04

Why do you think is_even will always return True? If you haven't even worked out your thinking enough to actually write it down for us, then it's impossible for us to explain where it went wrong. Which leaves us asking if you even really thought it through. As software developers, we must have the ability to critique our own thinking (or sometimes the lack of our thinking). I'm afraid I must downvote for not doing so. Also, what did the duck say?

– jpmc26
Jun 8 '17 at 0:24

|
show 9 more comments

5 Answers
5

active

oldest

votes

It always helps to decompose a recurrence relation till you find its base case.

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

In general, from your recurrence functions, it is easy to observe that is_even(n) will return [not not not ... n times] True, while is_odd(n) will return [not not not ... n - 1 times] True. So the number of nots and hence the final expression depend on n (aha!). Well, that's certainly a roundabout way of asking whether

n % 2 == 0

edited Jan 1 at 16:11

answered Jun 7 '17 at 22:08

coldspeed

135k23145230

add a comment |

Add a couple of print statements and you will see what it is doing:

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

edited Jun 8 '17 at 1:51

answered Jun 7 '17 at 22:19

AChampion

21.4k32345

The question wasn't tagged python-3.x so probably better to include a from __future__ import print_function at the top.

– MSeifert
Jun 7 '17 at 22:28

Good point, was following OP's print() statements.

– AChampion
Jun 8 '17 at 1:50

add a comment |

Like in most cases it might be helpful to include simply prints to follow the execution:

def is_even(x):

    print('check if {} is even'.format(x))

    if x == 0:

        return True

    else:

        return is_odd(x-1)



def is_odd(x):

    print('check if {} is odd'.format(x))

    return not is_even(x)

Then in your cases:

>>> print(is_even(2))

check if 2 is even

check if 1 is odd

check if 1 is even

check if 0 is odd

check if 0 is even

True



>>> print(is_odd(2))

check if 2 is odd

check if 2 is even

check if 1 is odd

check if 1 is even

check if 0 is odd

check if 0 is even

False

So basically it decrements the number until it's 0. The point is just how many nots have been accumulated in the is_odd calls. If it's an even number of nots then the result will be True, otherwise False.

answered Jun 7 '17 at 22:06

MSeifert

77.1k18148183

add a comment |

That's true; the recursion is supposed to end inside is_even.

And when that will happen, you'll know that the number you have is 0.

Now lets go backwards. This final state will be achieved by two cases - direct call to is_even(0) or a call from is_odd(0). In the first case - the result is all good. In the second - the result will be returned to the is_odd function, negated, and therefore will be falsy - giving a correct result.

Now, here the missing piece comes - the recursion: in order to reach this state, we need to decrease the argument each time, passing it through the opposite function - and that's exactly what we get with return is_odd(x-1).

Note: eventually this recursion leads to a chain of negations of the value True returned by the is_even. This chain is of length x where x is your number, and therefore odd or even in correspondence.

Therefore, the following code will do the same (lacking the is_odd nice side effect):

def is_even (x):

    res = True

    while x:

        res = not res

        x -= 1

    return res

edited Jun 7 '17 at 22:12

answered Jun 7 '17 at 22:06

Uriel

11k31738

add a comment |

I think that all the other answers are great but potentially the easiest way to understand the problem is how many times the answer will get "not"ed. Every time it passes through the is_odd function a not will be added on to the final answer. True will always be returned but for even numbers, there will always be an even number of nots which cancel each other out, but for odd numbers they will always have an odd number of nots and therefore return false.

answered Jun 7 '17 at 22:15

JoshKopen

750518

add a comment |

Your Answer

StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});

}
});

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f44423482%2frecursively-checking-for-odd-or-even%23new-answer', 'question_page');
}
);

Post as a guest

Name

Required, but never shown

5 Answers
5

active

oldest

votes

5 Answers
5

active

oldest

votes

It always helps to decompose a recurrence relation till you find its base case.

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

n % 2 == 0

edited Jan 1 at 16:11

answered Jun 7 '17 at 22:08

coldspeed

135k23145230

add a comment |

It always helps to decompose a recurrence relation till you find its base case.

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

n % 2 == 0

edited Jan 1 at 16:11

answered Jun 7 '17 at 22:08

coldspeed

135k23145230

add a comment |

It always helps to decompose a recurrence relation till you find its base case.

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

n % 2 == 0

edited Jan 1 at 16:11

answered Jun 7 '17 at 22:08

coldspeed

135k23145230

It always helps to decompose a recurrence relation till you find its base case.

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

n % 2 == 0

edited Jan 1 at 16:11

answered Jun 7 '17 at 22:08

coldspeed

135k23145230

edited Jan 1 at 16:11

answered Jun 7 '17 at 22:08

coldspeed

135k23145230

answered Jun 7 '17 at 22:08

coldspeed

135k23145230

answered Jun 7 '17 at 22:08

coldspeed

135k23145230

add a comment |

Add a couple of print statements and you will see what it is doing:

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

edited Jun 8 '17 at 1:51

answered Jun 7 '17 at 22:19

AChampion

21.4k32345

The question wasn't tagged python-3.x so probably better to include a from __future__ import print_function at the top.

– MSeifert
Jun 7 '17 at 22:28

Good point, was following OP's print() statements.

– AChampion
Jun 8 '17 at 1:50

add a comment |

Add a couple of print statements and you will see what it is doing:

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

edited Jun 8 '17 at 1:51

answered Jun 7 '17 at 22:19

AChampion

21.4k32345

The question wasn't tagged python-3.x so probably better to include a from __future__ import print_function at the top.

– MSeifert
Jun 7 '17 at 22:28

Good point, was following OP's print() statements.

– AChampion
Jun 8 '17 at 1:50

add a comment |

Add a couple of print statements and you will see what it is doing:

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

edited Jun 8 '17 at 1:51

answered Jun 7 '17 at 22:19

AChampion

21.4k32345

Add a couple of print statements and you will see what it is doing:

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

edited Jun 8 '17 at 1:51

answered Jun 7 '17 at 22:19

AChampion

21.4k32345

edited Jun 8 '17 at 1:51

answered Jun 7 '17 at 22:19

AChampion

21.4k32345

answered Jun 7 '17 at 22:19

AChampion

21.4k32345

answered Jun 7 '17 at 22:19

AChampion

21.4k32345

The question wasn't tagged python-3.x so probably better to include a from __future__ import print_function at the top.

– MSeifert
Jun 7 '17 at 22:28

Good point, was following OP's print() statements.

– AChampion
Jun 8 '17 at 1:50

add a comment |

The question wasn't tagged python-3.x so probably better to include a from __future__ import print_function at the top.

– MSeifert
Jun 7 '17 at 22:28

Good point, was following OP's print() statements.

– AChampion
Jun 8 '17 at 1:50

The question wasn't tagged python-3.x so probably better to include a from __future__ import print_function at the top.

– MSeifert
Jun 7 '17 at 22:28

Good point, was following OP's print() statements.

– AChampion
Jun 8 '17 at 1:50

add a comment |

Like in most cases it might be helpful to include simply prints to follow the execution:

def is_even(x):

    print('check if {} is even'.format(x))

    if x == 0:

        return True

    else:

        return is_odd(x-1)



def is_odd(x):

    print('check if {} is odd'.format(x))

    return not is_even(x)

Then in your cases:

>>> print(is_even(2))

check if 2 is even

check if 1 is odd

check if 1 is even

check if 0 is odd

check if 0 is even

True



>>> print(is_odd(2))

check if 2 is odd

check if 2 is even

check if 1 is odd

check if 1 is even

check if 0 is odd

check if 0 is even

False

answered Jun 7 '17 at 22:06

MSeifert

77.1k18148183

add a comment |

Like in most cases it might be helpful to include simply prints to follow the execution:

def is_even(x):

    print('check if {} is even'.format(x))

    if x == 0:

        return True

    else:

        return is_odd(x-1)



def is_odd(x):

    print('check if {} is odd'.format(x))

    return not is_even(x)

Then in your cases:

>>> print(is_even(2))

check if 2 is even

check if 1 is odd

check if 1 is even

check if 0 is odd

check if 0 is even

True



>>> print(is_odd(2))

check if 2 is odd

check if 2 is even

check if 1 is odd

check if 1 is even

check if 0 is odd

check if 0 is even

False

answered Jun 7 '17 at 22:06

MSeifert

77.1k18148183

add a comment |

Like in most cases it might be helpful to include simply prints to follow the execution:

def is_even(x):

    print('check if {} is even'.format(x))

    if x == 0:

        return True

    else:

        return is_odd(x-1)



def is_odd(x):

    print('check if {} is odd'.format(x))

    return not is_even(x)

Then in your cases:

>>> print(is_even(2))

check if 2 is even

check if 1 is odd

check if 1 is even

check if 0 is odd

check if 0 is even

True



>>> print(is_odd(2))

check if 2 is odd

check if 2 is even

check if 1 is odd

check if 1 is even

check if 0 is odd

check if 0 is even

False

answered Jun 7 '17 at 22:06

MSeifert

77.1k18148183

Like in most cases it might be helpful to include simply prints to follow the execution:

def is_even(x):

    print('check if {} is even'.format(x))

    if x == 0:

        return True

    else:

        return is_odd(x-1)



def is_odd(x):

    print('check if {} is odd'.format(x))

    return not is_even(x)

Then in your cases:

>>> print(is_even(2))

check if 2 is even

check if 1 is odd

check if 1 is even

check if 0 is odd

check if 0 is even

True



>>> print(is_odd(2))

check if 2 is odd

check if 2 is even

check if 1 is odd

check if 1 is even

check if 0 is odd

check if 0 is even

False

answered Jun 7 '17 at 22:06

MSeifert

77.1k18148183

answered Jun 7 '17 at 22:06

MSeifert

77.1k18148183

answered Jun 7 '17 at 22:06

MSeifert

77.1k18148183

answered Jun 7 '17 at 22:06

MSeifert

77.1k18148183

add a comment |

That's true; the recursion is supposed to end inside is_even.

And when that will happen, you'll know that the number you have is 0.

Therefore, the following code will do the same (lacking the is_odd nice side effect):

def is_even (x):

    res = True

    while x:

        res = not res

        x -= 1

    return res

edited Jun 7 '17 at 22:12

answered Jun 7 '17 at 22:06

Uriel

11k31738

add a comment |

That's true; the recursion is supposed to end inside is_even.

And when that will happen, you'll know that the number you have is 0.

Therefore, the following code will do the same (lacking the is_odd nice side effect):

def is_even (x):

    res = True

    while x:

        res = not res

        x -= 1

    return res

edited Jun 7 '17 at 22:12

answered Jun 7 '17 at 22:06

Uriel

11k31738

add a comment |

That's true; the recursion is supposed to end inside is_even.

And when that will happen, you'll know that the number you have is 0.

Therefore, the following code will do the same (lacking the is_odd nice side effect):

def is_even (x):

    res = True

    while x:

        res = not res

        x -= 1

    return res

edited Jun 7 '17 at 22:12

answered Jun 7 '17 at 22:06

Uriel

11k31738

That's true; the recursion is supposed to end inside is_even.

And when that will happen, you'll know that the number you have is 0.

Therefore, the following code will do the same (lacking the is_odd nice side effect):

def is_even (x):

    res = True

    while x:

        res = not res

        x -= 1

    return res

edited Jun 7 '17 at 22:12

answered Jun 7 '17 at 22:06

Uriel

11k31738

edited Jun 7 '17 at 22:12

answered Jun 7 '17 at 22:06

Uriel

11k31738

answered Jun 7 '17 at 22:06

Uriel

11k31738

answered Jun 7 '17 at 22:06

Uriel

11k31738

add a comment |

answered Jun 7 '17 at 22:15

JoshKopen

750518

add a comment |

answered Jun 7 '17 at 22:15

JoshKopen

750518

add a comment |

answered Jun 7 '17 at 22:15

JoshKopen

750518

answered Jun 7 '17 at 22:15

JoshKopen

750518

answered Jun 7 '17 at 22:15

JoshKopen

750518

answered Jun 7 '17 at 22:15

JoshKopen

750518

answered Jun 7 '17 at 22:15

JoshKopen

750518

add a comment |

draft saved

draft discarded

Thanks for contributing an answer to Stack Overflow!

Please be sure to answer the question. Provide details and share your research!

But avoid …

Asking for help, clarification, or responding to other answers.

Making statements based on opinion; back them up with references or personal experience.

To learn more, see our tips on writing great answers.

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Post as a guest

Name

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Name

Required, but never shown

Name

Required, but never shown

This page is only for reference, If you need detailed information, please check here

Search This Blog

Ufyukyu