Recursion in python3

Question

def r(s):

    if s=="":
        return ""
    else:
        return r(s[1:])+s[0]


r("ollah")

why is only s[0] returned and r(s[1:]) not? can someone explian this Code to me?

Answer 1

Your code in the form presented in your question works correctly. (Maybe you don't express your question accordingly.) So I will jump into the explanation:

I want to reverse a string (e.g."abcde"). I may do it in this manner:

1. I divide this string into 2 parts:
   1. the first character (a) — I will call it a head, and
   2. the remaining characters (bcde) — I will call it a tail.

2. Then I simply:
   1. reverse the tail by some "magic" function r()- I will obtain edcb, and
   2. append the head to it — I will obtain edcba, a thing, what I wanted.

Written in Python (in a detailed form):

head = s[0]               # first character (of the string s)
tail = s[1:]              # second character to last character (of the same string)

reversedTail = r(tail)    # use of a "magical" function r()

reversedString = reversedTail + head

It doesn't matter if I perform it in a compact, one-line form

revesedString = r(s[1:]) + s[0]      # reversed tail appended by head

---

Now the “only” problem is how to reverse the tail!

But while string "abcde" had 5 characters, the tail "bcde" has only 4 of them.

To reverse bcde, I will follow the same idea:

1. I divide it into a head (b) and a tail (cde), then
2. I reverse the tail by the “magical” function r() to obtain edc, and append the head (b).

The result will be edcb — exactly what I wanted.

---

Here raised a similar problem — how to reverse now only 3-character long string "cde"?

The solution is the same: dividing into a head (c) and a tail (de), reversing the tail and append the head to it. The result: edc, what I wanted.

---

But how to reverse 2-character long string "de"? You already know — by dividing it into a head (d) and a tail (e), reversing the tail and append the head to it, obtaining ed.

---

Now the most difficult task — how to reverse the 1-character long string "e"?

You know — dividing it into a head (e) and a tail — but the tail is now an empty string (""). By reverting an empty string we obtain the same empty string, which is in your program expressed as

if s=="":
    return ""

So the "magical" function is not as magical as it seems - it relies on dividing the original string into a head and a tail, and then recursively on dividing the tail into another head and tail. The last tail is an empty string, and the recursion ends here. (From the other point of view, the computation just begins.)

Only the tail is passed (as an input parameter) to the magical function r() (in the form return r(tail) + head) — progressively shorter and shorter: