CODEWITHSUNDEEP
python
VPNTIME
VPNTIME

Reputation: 761

Why does this output occur?

def function(s):
 if len(s) == 1:
    print s[0],
 else:
    function(s[1:])
    print s[0],

function("1234") ends up printing 4 3 2 1

Why does this happen? In the function, obviously the first condition is not met. In the else condition, s[1:] is put in for s, yet its length is not 1. I just don't see how anything outside of s[0] would be printed to the screen. There's nothing in that function that looks like it'd print s[1:], let alone in reverse. I'm pretty confused.

Upvotes: 2

Views: 211

Answers (4)

Levon
Levon

Reputation: 143027

This is a case of recursion, you are calling the function itself over and over with shorter and shorter substrings of the original input, until it is a string of length 1 (the last one in the original input) in which case it starts printing it and then "unwinding" and printing the rest of the string in reverse.

Take a look at this annoted code:

def function(s):
    if len(s) == 1:
        print 'single:', s[0],  # (A) this is where your first output is generated for a single character
    else:
        print 'calling function again with ',s[1:]
        function(s[1:]) # (B) you call function again, i.e., your recursive call
        print ' unwind->', s[0], # (C) the "unwinding" step, i.e, finish the rest
                                 # of the function when you return from the recursive call

the output you get is:

calling function again with 234
calling function again with 34
calling function again with 4
single: 4  unwind-> 3  unwind-> 2  unwind-> 1

The first time you call the function you drop through to the else clause and in line (B) you call the function again, but this time with "234". Now the function starts again but with "234" and again you drop through to the else and now call function again, but now with "34", function runs again, now with you drop through to the else once more and call function with just "4" .. this time since it's of length 1, you print it (line A).

Now you return from this function (the unwinding process) - and resume from the point where you were before you made your recursive call and you print the rest of the string in reverse by printing the first character of the current remaining character (line C).

Recursion can be hard to grasp the first time you encounter it - that's perfectly normal. At some point it will click and become clear. You may want to do some reading about the general concept and search for some clear annotated examples (most CS/programming books will have some).

Here is a short YouTube video that explains recursion in Python with a simple example, hope it helps: http://www.youtube.com/watch?v=72hal4Cp_2I

Upvotes: 1

R Samuel Klatchko
R Samuel Klatchko

Reputation: 76541

Let's watch recursion in work.

  • First you call function with s="1234"
  • len(s) = 4 so you take the else
  • You call function recursively with s[1:] or "234"
    • Now, you are in function with s="234"
    • len(s) = 3 so you take the else
    • You call function recursively with s[1:] or "34"
      • Now, you are in function with s="34"
      • len(s) = 2 so you take the else
      • You call function recursively with s[1:] or "34"
        • Now, you are in function with s4"
        • len(s) = 1 so you do the first part of the if and and print s[0] i.e. 4
        • You return
      • Returning to previous call (s="34") you print s[0], i.e. 3
      • You return
    • Returning to previous call (s="234") you print s[0], i.e. 2
    • You return
  • CReturning to previous call (s="1234") you print s[0], i.e. 1
  • You return

Upvotes: 0

Larry Lustig
Larry Lustig

Reputation: 50970

Try modifying the function like this:

def function(s):
   print 'Called with {}'.format(s)
   if len(s) == 1:
      print s[0]
   else:
      function(s[1:])
      print s[0]

and running it. You'll see that each time you hit function(s[1:]) you're suspending that "run" of function() and starting a new run of function() inside the now-temporarily-suspended one. The new call to function() uses a shortened version of the string. Eventually, it's called with only a single character and you hit the first condition.

Calling a function from inside itself is called recursion.

Upvotes: 1

Nolen Royalty
Nolen Royalty

Reputation: 18633

>>> def function(s):
...     print 's is currently %r' % s
...     if len(s) == 1:
...         print s[0],
...     else:
...         function(s[1:])
...         print s[0],
... 
>>> function("1234")
s is currently '1234'
s is currently '234'
s is currently '34'
s is currently '4'
4 3 2 1

It's a recursive function, and it calls itself again before it prints s[0] so the items that it prints out are reversed.

Here is an example that might be more helpful.

>>> def function(s):
...     print 's is currently %r' % s
...     if len(s) > 1:
...         print 'calling function again with %r as s' % s[1:]
...         function(s[1:])
...     print s[0],
... 
>>> function('1234')
s is currently '1234'
calling function again with '234' as s
s is currently '234'
calling function again with '34' as s
s is currently '34'
calling function again with '4' as s
s is currently '4'
4 3 2 1

Upvotes: 9

Related Questions