-1

So I'm talking to a friend about the following function. Lets suppose that the input to the function is 100. One says that this would print 100, 50, 25, 12, 6, 3, 1, 1 while the other one argues that it should print 100, 101, 50, 51, and so on. I tried to run it to see the result myself, however I have no experience in Python and this is just an exercise from a textbook and when I tried to run it on ideone it didn't provide any output. Thanks!

def CodeWrite (N):

    if (N > 0):
        print(N)
        CodeWrite(N / 2)
    print(N + 1)
Szymon
  • 42,577
  • 16
  • 96
  • 114
ch15
  • 81
  • 1
  • 8
  • 1
    Write it to a file, say `foo.py` and then run it... `python foo.py`. Let python tell you who is right. – tdelaney Dec 21 '15 at 04:15
  • and you will probably hit a 'maximum recursion depth exceeded while pickling an object' error :) .. you probably want to have a better termination condition. – astrosyam Dec 21 '15 at 04:17
  • It depends -- if you run on Python 3, `N / 2` produces floating point. – dawg Dec 21 '15 at 04:17
  • 1
    Sorry i have to downvote this but the basic premise would have been easy to verify by yourself. Even the different behaviour between python2 and 3 is easy to google and find out by yourself. – RedX Dec 21 '15 at 04:23
  • @tdelaney so I downloaded python 2, wrote this same thing on a file, called it hello.py and did that in the terminal. Nothing happened. I also declared N = 100 inside the file yet nothing happened. – ch15 Dec 21 '15 at 04:26
  • @RedX I know and I looked for information on both, and I tried to run it myself by I have no prior experience with python. Downloaded it, saved it into a file, tried to run it from terminal but no output was produced. That's why I decided to ask here. – ch15 Dec 21 '15 at 04:27
  • 1
    At the end of the file you wrote, add a line: `CodeWrite(100)`. It should be all the way to the left - not indented with the function. You have to call the function before it runs. – tdelaney Dec 21 '15 at 04:29
  • For a simple online python 3 interface https://repl.it/ – RedX Dec 21 '15 at 04:30
  • @TigerhawkT3 - Is this question a duplicate? This has nothing to do with functions not being called; it is rather a question about recursion. – Patrick Yu Dec 21 '15 at 05:36
  • @PatrickYu - "when I tried to run it on ideone it didn't provide any output", and see tdelaney's comment above. All the OP needed was to run it, and then they would've seen the output for themselves. – TigerhawkT3 Dec 21 '15 at 05:43

3 Answers3

3

If you run it on Python 2.7, you can easily see that the output is:

100
50
25
12
6
3
1
1
2
4
7
13
26
51
101

This is because it first print all the numbers going deep into recursion. Then it prints them in reverse order, adding one to each.

The recursion stops at 1, because in Python 2.7 1 / 2 gives the result of 0.

For Python 3, it will most likely get RuntimeError: maximum recursion depth exceeded while calling a Python object error as the division produces floating point numbers and won't stop at a low number of recursions.

You can check the difference in division in Python 2 and 3, for example in this question and answers: Division in Python 2.7. and 3.3

Community
  • 1
  • 1
Szymon
  • 42,577
  • 16
  • 96
  • 114
2

Yes, it will divide N by 2 until 0, but then it will start going outwards and calling N+1 when the program has done its recursive calls.

When calling CodeWrite(100), you get a long stream of numbers:

>>> CodeWrite(100)
100
50
25
12
6
3
1
1
2
4
7
13
26
51
101

We can simplify it by looking at the trace of the calls:

CodeWrite(100)
  CodeWrite(50)
    CodeWrite(25)
      CodeWrite(12) #Because integer division, 25/2 = 12.5 -> 12
        CodeWrite(6)
          CodeWrite(3)
             CodeWrite(1) #3/2 = 1.5, truncated to 1
                CodeWrite(0) #1/2 = 0.5, truncated to 0
                #Stops calling N > 0, since N == 0
                print(0+1) -> 1
             print(1+1) -> 2
          print(3+1) -> 4
         print(6+1) -> 7
       print(12+1) -> 13
     print(25+1) -> 26
   print(50+1) -> 51
 print(100+1) -> 101
Patrick Yu
  • 972
  • 1
  • 7
  • 19
1

Already answered but to clarify about what you actually asked:

Is print (N + 1) called every time the function is called or does it only print until N is 0?

Everytime N is greater than 0, it prints N and executes CodeWrite(N / 2), so basically to the top of the function, if you want to think of it that way.

When N is not greater than 0, it then goes to print(N + 1) and leaves the function and returns. In the previous recursions, it comes back where it left off after CodeWrite(N / 2) and prints N+1. Same thing happens for all previous recursive calls, and in reverse since it's returning from the last calls.

aneroid
  • 12,983
  • 3
  • 36
  • 66
  • Thanks for the explanation! It is very clear now – ch15 Dec 21 '15 at 04:37
  • 1
    Welcome to SO. Typically you should Upvote answers which were helpful and Accept the best one for you. You've done the latter, so good start. – aneroid Dec 21 '15 at 04:40