Why does this output occur?

Question

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.

Answer 1

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

Answer 2

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

• VPNTIME: I'm still lost. I don't really understand recursion, either. Isn't it if you call the function again, it would just keep calling it and nothing would be printed because the length of s[1:] is never 1?
• lvc: @Omerta what you are missing is that s is a different s each time function gets called. Once you have that, len(s[1:]) does, eventually, go to 1.
• VPNTIME: Thanks Levon. I really do get it now.
• Levon: @Omerta Happy to hear that. If this was helpful please feel free to upvote this and if it answered your question select it as your answer by checkmarking it.
• VPNTIME: @Levon. I dont have enough rep for that.

Answer 3

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.

Answer 4

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