Welcome to the Treehouse Community

Want to collaborate on code errors? Have bugs you need feedback on? Looking for an extra set of eyes on your latest project? Get support with fellow developers, designers, and programmers of all backgrounds and skill levels here with the Treehouse Community! While you're at it, check out some resources Treehouse students have shared here.

Looking to learn something new?

Treehouse offers a seven day free trial for new students. Get access to thousands of hours of content and join thousands of Treehouse students and alumni in the community today.

Start your free trial

Python

Posted by Akash malhotra
Akash malhotra
3,025 Points

Reverse string using recursion

I'm trying to reverse a basic string using recursion in pyhon. I get an error "RuntimeError: maximum recursion depth exceeded".What's wrong with my method, the logic seems fine to me.

def reverse(t):
    return reverse(t[1:])+t[0]
print(reverse('hello world'))

2 Answers

Stone Preston
Stone Preston
42,016 Points
Stone Preston
Stone Preston
42,016 Points

You need to check if t is empty first

def reverse(t):
  if t == "":
    return t
  else:
    return reverse(t[1:]) + t[0]
print(reverse('hello world'))

Solution found here

Akash malhotra
Akash malhotra
3,025 Points

Can you explain why that is neccesary? Like I understand that it's good to check,but why can't we just return it, assuming that 't' is not empty.

Stone Preston
Stone Preston
42,016 Points

Honestly im not too sure. Dont use recursion much. I added some print calls to see what it actually looks like as it goes through the string:

def reverse(t):
  print("t = " + t)
  if t == "":
    print("t is empty")
    return t
  else:
    return reverse(t[1:]) + t[0]
print(reverse('hello world'))

and got 

t = hello world
t = ello world
t = llo world
t = lo world
t = o world
t =  world
t = world
t = orld
t = rld
t = ld
t = d
t = 
t is empty
dlrow olleh

so it looks like the empty string at the end causes the function to get stuck in a recursive loop. the check provides a way to break out of the recursion

Caleb Kleveter
MOD
Caleb Kleveter
Treehouse Moderator 37,862 Points
Caleb Kleveter
Caleb Kleveter
Treehouse Moderator 37,862 Points

Is the reason is you can't reverse a empty string? I'm having trouble understanding the function, but that might be why.

Akash malhotra
Akash malhotra
3,025 Points

So If I'm understanding this right, this is how recursion is working right? ( I'm just using 'hello' instead of 'hello world')

 = reverse(ello) + h           # The recursive step
 = reverse(llo) + e + h
 = reverse(lo) + l + e + h
 = reverse(o) + l + l + e + h  # Base case
 = o + l + l + e + h
 = olleh
Caleb Kleveter
Caleb Kleveter
Treehouse Moderator 37,862 Points

I'm not sure, I don't know to much python, or recursion.