What does [1:] do in a recursive function

user_14658057 0
Viewed 62

I saw this used in code and I didn't understand how it worked. Does it save what it chops off somewhere?

here is an example (from askpython):

def rev_string(x): 
    if len(x) == 0: 
        return x 
    else: 
        return rev_string(x[1:]) + x[0] 
   
x = "STRING"
   
print ("Original string: ") 
print (x) 
   
print ("Reversed string: ") 
print (rev_string(x))

it seems like it chops off the first character each recursion, which disappears until almost the end when it repeats the "+ x[0]" part all at once for all of the letters.

How does it work?

list python
2 Answers

Since x[1:] gets all but the first item of the list, and x[0] gets only the first item, we can assume that the way this recursion works is that it does this repeatedly for each value of x[1:], which will decrease in length by one with each successive iteration, since it's calling itself with the sliced list.

Therefore, the end result is that the string is reversed.

If we call your function with "STRING", these are the steps:

rev_string(x="STRING")
rev_string(x[1:]) + x[0] # equivalent to rev_string("TRING") + "S"
rev_string("RING") + "T"
rev_string("ING") + "R"
rev_string("NG") + "I"
rev_string("G") + "N"

# the final call to rev_string results in:
return "G"

# meaning that the result of the previous call is:
return "G" + "N"

# meaning the previous call results in:
return "GN" + "I"

# and then:
return "GNI" + "R"

# and then:
return "GNIR" + "T"

# and then:
return "GNIRT" + "S"

# and then:
return "GNIRTS"
user_62732510

It basically calls the function with a new string formed by all the characters but the first one. The x[1:] is a slice operation that returns all the elements from index 1 (second element) up to the end.

Note that in rev_string(x[1:]) + x[0], such first character is appended at the end. As the string is being reduced one character every call (until it becomes empty), it is reversing the string (as the method names indicates).

Here an example of calling rev_string("Hello"). First, the sequence downwards:

x = "Hello" -> x[1:] = "ello", x[0] = "H"
x = "ello" -> x[1:] = "llo", x[0] = "e"
x = "llo" -> x[1:] = "lo", x[0] = "l"
x = "lo" -> x[1:] = "o", x[0] = "l"
x = "o" -> x[1:] = "", x[0] = "o"

Then the rollback:

"" + "o" = "o"
"o" + "l" = "ol"
"ol" + "l" = "oll"
"oll" + "e" = "olle"
"olle" + "H" = "olleH"
user_14858850
Related