12

I am trying to write a recursive function that prints from 0 to n, but I have no idea how to do it. I accidentally made one that prints from n to 0 though:

def countdown(n):
    print(n)
    if n == 0:
        return 0
    return countdown(n - 1)

I don't know if that helps or not, maybe I can change something in the code to make it go from 0 to n?

baduker
  • 19,152
  • 9
  • 33
  • 56
user2489526
  • 161
  • 2
  • 3
  • 8

6 Answers6

17

You're about 99% there.

Think of your base case and your recursive step - when you hit 0, what do you want to do? When you're still working your way down from n, what do you want to happen?

If you reverse the order in which you print the value, you'll reach your desired result.

def countdown(n):
    if n != 0:
        countdown(n-1)
    print(n)

The reason this works is that recursive calls go on the call stack. As you push calls onto the stack, while your end case isn't met, you'll keep adding more calls until you reach your base case of n == 0, and then you'll exclusively start printing the values.

The other calls will then fall through to the print statement, as their execution has returned to the line after the conditional.

So, the call stack looks something like this:

countdown(5)
    countdown(4)
        countdown(3)
            countdown(2)
                countdown(1)
                    countdown(0)
                    print(0)
                print(1)
            print(2)
         print(3)
     print(4)
print(5)
Makoto
  • 104,088
  • 27
  • 192
  • 230
  • And it does. This prints 0 1 2 3 4 5, all on separate lines. If this were counting down, it would be printing 5 4 3 2 1 0, on separate lines. – Makoto Jun 15 '13 at 20:11
  • 2
    Your solution requires O(n) memory unnecessary. @Andy Hayden provides a way to do it in O(1) memory (just add tail_call decorator). [Look at two pictures in SICP](http://mitpress.mit.edu/sicp/full-text/sicp/book/node15.html) to understand the difference (your answer is the first picture) – jfs Jun 15 '13 at 20:19
  • 1
    @J.F.Sebastian I don't see how Andy's solution uses less memory. Both solutions will use `n` stack frames, but Andy's has two local variables per frame, whereas this only has one. – Aya Jun 15 '13 at 20:35
  • @J.F.Sebastian thanks for the excellent article, this explains why Peter Norvig uses that method... :) – Andy Hayden Jun 15 '13 at 20:42
  • 1
    @Aya: notice: "add tail_call decorator" part, [here's an example](http://ideone.com/O8E43w). Also, it is not practical to use any recursive solution for the problem so I consider that Python is used as an executable pseudo-code in the question i.e., some general computation model is assumed where function calls are not expensive and a trivial tail call elimination may exist. – jfs Jun 15 '13 at 21:12
  • 1
    @J.F.Sebastian +1 Interesting, but if you hack around the stack like that, it's not technically a recursive function any more, at least by any meaningful definition. So, IMO, it's just as valid as an iterative solution along the lines of: `for i in xrange(10): print i` which would use even less memory. Regarding practicality, you can always substitute stack recursion for heap recursion, or use [Stackless Python](http://en.wikipedia.org/wiki/Stackless_Python), but I agree that recursion is inappropriate in this case. However, it's purely academic, and not something you'd ever do in practice. – Aya Jun 16 '13 at 14:21
  • @Aya: it does not matter *how* the decorator is implemented. The important part is that it *can* be applied. Here's [a video that explains the difference between solutions (their shapes) (in the same way as the pictures I've linked (by the same authors))](http://youtube.com/watch?v=dlbMuv-jix8). – jfs Jun 16 '13 at 15:27
  • @J.F.Sebastian Looks as if the video agrees with my assessment. The lecturer even defines the first model as "iteration" (as opposed to "recursion") at ~27:45 in the video, and the rationale for using tail 'recursion' is [apparently](http://en.wikipedia.org/wiki/Scheme_programming_language#Proper_tail_recursion) just idiomatic to Scheme, presumably because of its requirement to support tail call optimization, which doesn't really apply to Python. I guess you can use such a decorator to make Python behave more like Scheme, but it feels like an antipattern to me. – Aya Jun 16 '13 at 18:01
  • @Aye: all this problem (expressing iteration using recursion) needs is a simple substition model formulated in the video. Syntax, semantics, implementation details of particular languages do not matter. Consider any resemblence to Python or Scheme to be accidental. [\[Computer science\] is not really about computers -- and it's not about computers in the same sense that physics is not really about particle accelerators...](http://en.wikiquote.org/wiki/Computer_science) – jfs Jun 16 '13 at 18:52
  • I'm glad that the both of you like this discussion, but let's establish two things: 1) Let's not have it in my global inbox, and 2) It's my opinion that, if a tail-recursion optimized solution is *desired*, then Python is the wrong language to do it in. To make it use O(1) space while iterating in this problem context, then a simple loop would be *vastly* superior. I see no benefit in introducing syntax that a beginner would blindly apply to make up for an intentional deficit in this language, just to satisfy the sciences. – Makoto Jun 16 '13 at 19:38
14

You almost got it! here's a fixed, simplified version:

def countup(n):
    if n >= 0:
        countup(n - 1)
        print(n)

Notice that:

  • You don't have to return anything from a recursive function that only prints values
  • For printing in ascending order, the print statement must be placed after the recursive call
  • The recursion exits when n < 0, given that we're only printing, there's nothing left to be done afterwards and it's ok to return None (Python's default return value)

UPDATE

It seems that writing a tail recursive solution is all the rage around here :) oh well, here's my shot at it, a simplified and tail-recursive version of @AndyHayden's idea - using the tail call optimization decorator recipe:

@tail_call_optimized
def countup(N, n=0):
    print(n)
    if n < N:
        countup(N, n + 1)

Either way, it works as expected:

countup(5)
=> 0
   1
   2
   3
   4
   5
Óscar López
  • 232,561
  • 37
  • 312
  • 386
3

You can replace the 0 and the n, and the + with a - to make your recursive countdown function to a recursive countup:

def countup(N, n=0):
    print(n)
    if n == N:
        return
    return countup(N, n + 1)

And call it as follows:

countup(3)

@JFSebastian points out this algorithm has the benefit of being O(1) rather than O(n), as discussed in this excellent article about the difference between a linear and iterative recursion, if used with the @tail_call_optimized decorator.

Andy Hayden
  • 359,921
  • 101
  • 625
  • 535
0

You can do this

def fun(num,n):
    if num<n:
        print(num)
        fun(num+1,n)
n=int(input())
print(fun(0,n+1))
Baishakhi Dasgupta
  • 143
  • 4
0

you can try this method as well:

def recursion_print(n):
    if n==0:
      print(n)
    else:
      recursion_print(n-1)
      print(n)


recursion_print(9)
raj
  • 41
  • 2
0

It should be best answer from my side.I hope u like this

 def countdown(n): 
    if n >0:    #this condition if n is greater than 0 untill run the program.
        countdown(n-1)   #this is recursion (calling itself).
    print(n)   #print the numbers.
countdown(10)   #function arguments.
Jitendra chouhan
  • 5
  • 2