Reverse string recursive function loop

Question

Where is the break criteria in this recursive function? Why doesn't this go on endlessly reversive characters of the string?

print('Enter your input:')
n = input()

def reverse(s):
    if len(s) == 0:
        return s
    else:
        return reverse(s[1:]) + s[0]

print (reverse(n))

Enter your input:
Something
gnihtemoS

mattroberts · Accepted Answer · 2019-11-15 03:18:05Z

1

When the String is of length 0, you make a non-recursive return, causing the recursive calls on the stack to return until you get all the way to the bottom of them.

answered Nov 15, 2019 at 3:18

mattroberts

6301 gold badge7 silver badges13 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

kaya3 · Accepted Answer · 2019-11-15 03:19:15Z

0

A recursive function terminates if it satisfies two properties:

There must be a "base case" which is solved without any recursive calls, and
Each recursive call must be on an input which is "closer" to the base case than before.

In this recursive function, the base case is the empty string; it is handled by return s without making any recursive calls. The recursive call is on the string s[1:] which is one character shorter than s, so it is "closer" to the empty string. Therefore the function satisfies both of these properties, so it always terminates.

answered Nov 15, 2019 at 3:19

kaya3

51.6k7 gold badges87 silver badges118 bronze badges

Collectives™ on Stack Overflow

Reverse string recursive function loop

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related