Reversing the order

Question

I'm new to python and not really good with recursion so if some kindly help me with this problem, it will be greatly appreciated. So I'm basically trying to reverse the order of the string. For example, if the string is" It's me" it should return "me It's". Although, I'm getting a completely reversed string and for most part I'm getting an error saying the second function is not defined.

def reverse_phrase(str):
    reverse_phrase_recursive(str.split())

def reverse_phrase_recursive(str):
    if len(str)==0:
        return str
    else:
        return reverse_phrase(str[1:]) + str[0]
        
print(reverse_phrase("DO I CHOOSE YOU PIKACHU"))

Error I get for reference: `AttributeError: 'list' object has no attribute 'split'` — SuperStormer, Mar 12 '21 at 23:22
Your `reverse_phrase_recursive` needs to call `reverse_phrase_recursive`, not `reverse_phrase`. `r_p` expects a string, `r_p_r` expects a list. If you then change `reverse_phrase` to `return ' ',.join(reverse_phrase_recursive(str.split())`, it will work. — Tim Roberts, Mar 12 '21 at 23:27
Yep, @SuperStormer is right. I printed the value of str when you call reverse_phrase the second time and it came back `['I', 'CHOOSE', 'YOU', 'PIKACHU']` — Eddie D, Mar 12 '21 at 23:28
Btw, this is a pretty expensive method of reversing a string. split is an iterative method. If my memory is correct it allocates new memory as well. Consider using an index reference that is passed down the iterations or you can check the length of your new string vs your old one as you work your way through it. There are a number of more efficient approches when using recursion — Eddie D, Mar 12 '21 at 23:30
I had tried what you guys said but I'm still getting TypeError: can only concatenate list (not "str") to list on return reverse_phrase_recursive(str[1:]) + str[0] — Brandon Oson, Mar 12 '21 at 23:36

score 1 · Answer 1 · answered Mar 12 '21 at 23:24

You need to call reverse_phrase_recursive as the recursive call, otherwise a list will be passed to reverse_phrase and then it will try to call .split() on a list, which throws an AttributeError.

Also, actually return the value from reverse_phrase and make the value concatted to the recursive call a list because you can't concat str to a list directly.

def reverse_phrase(str):
    return " ".join(reverse_phrase_recursive(str.split()))

def reverse_phrase_recursive(str):
    if len(str)==0:
        return str
    else:
        return reverse_phrase_recursive(str[1:]) + [str[0]]
        
print(reverse_phrase("DO I CHOOSE YOU PIKACHU"))

Side Note: don't name your variable "str", it overwrites the builtin str.

there are still errors that I can seem to understand whats causing them like TypeError: can only concatenate list (not "str") to list — Brandon Oson, Mar 12 '21 at 23:32

score 0 · Answer 2 · answered Mar 12 '21 at 23:24

0

def reverse_phrase(str):
    return ' '.join(reversed(str.split()))

answered Mar 12 '21 at 23:24

Tim Roberts

48,973
4
21
30

1

I had tried something like this already buy it need to be a recursive function – Brandon Oson Mar 12 '21 at 23:32
I figured as much. ;) – Tim Roberts Mar 12 '21 at 23:48
While this code may answer the question, providing additional context regarding why and/or how this code answers the question improves its long-term value. – Donald Duck Mar 13 '21 at 19:08

score 0 · Answer 3 · answered Mar 12 '21 at 23:29

0

Here is a solution for reversing:

def reverse(s): 
    return ' '.join(s.split()[::-1])

s = "DO I CHOOSE YOU PIKACHU" 
reverse(s)

#Output: 

'PIKACHU YOU CHOOSE I DO'

answered Mar 12 '21 at 23:29

Inputvector

1,061
10
22

score 0 · Answer 4 · answered Mar 12 '21 at 23:49

0

Here is a take on the recursion without having to do the whole split / join process. As I mentioned in a comment, it's expensive performance wise.


def reverse_phrase(str, reversedStr=""):
    if (len(reversedStr) == len(str)):
      return reversedStr;

    reversedStrLength = len(reversedStr);  
    index = len(str) - reversedStrLength - 1;
    reversedStr += str[index];

    return reverse_phrase(str, reversedStr);
   
        
print(reverse_phrase("DO I CHOOSE YOU PIKACHU"));

answered Mar 12 '21 at 23:49

Eddie D

1,120
7
16

Isn't string concatenation quadratic(and less efficient than a list)? Also, this is python, semicolons are unnecessary and snake_case > camelCase. – SuperStormer Mar 13 '21 at 00:05
Just checked with timeit, split+join is faster. split+join: `%timeit reverse_phrase("DO I CHOOSE YOU PIKACHU") 1.87 µs ± 72.4 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)`. str concatenation: `%timeit reverse_phrase2("DO I CHOOSE YOU PIKACHU") 8.8 µs ± 670 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)` – SuperStormer Mar 13 '21 at 00:09
Would that scale though as n approaches a much larger size? For example, if N has a length of 50K characters? – Eddie D Mar 13 '21 at 01:30
Actually, that would more than likely cause a stack overflow if we're using recursion unless Python3 supports TCO out of the box. – Eddie D Mar 13 '21 at 01:33
Also not familiar with what Python's approach on string concat is under the hood or if it supports allocating the string buffer the size of your final product? The initial approach is also using string concatenation isn't it? – Eddie D Mar 13 '21 at 01:40
OP is using *list* concatenation, which is different b/c lists are mutable and strings aren't. https://stackoverflow.com/questions/39312099/why-is-join-faster-than-in-python – SuperStormer Mar 13 '21 at 04:28

pakpe · Answer 5 · 2021-03-13T05:37:47.803

Here is another way to do this without using join. Your reverse_phrase() function calls the recursive function with a list of words. The base case of recursive function is when the length of the list is 2, in which case it swaps the the two words. Else, it swaps the last word of the list with the recursive output of all the initials words.

def reverse_phrase(str):
    return reverse_phrase_recursive(str.split())

def reverse_phrase_recursive(l):
    if len(l) == 2:
        return l[1] + " " + l[0]
    return l[-1] + " " + reverse_phrase_recursive(l[:-1])

print(reverse_phrase('this is a great recursive function'))
#function recursive great a is this

Mulan · Answer 6 · 2021-03-13T07:16:02.237

Here's another way that doesn't rely on built-in function .split -

def reverse_phrase(s):
  def loop(s, word, phrase):
    if not s:
      return word + " " + phrase                #1
    elif s[0] == " ":
      return loop(s[1:], "", word + " " + phrase) #2
    else:
      return loop(s[1:], word + s[0], phrase)       #3
  return loop(s, "", "")

print(reverse_phrase("DO I CHOOSE YOU PIKACHU"))

Evaluates as -

loop("DO I CHOOSE YOU PIKACHU", "", "")             #3
loop("O I CHOOSE YOU PIKACHU", "D", "")             #3
loop(" I CHOOSE YOU PIKACHU", "DO", "")           #2
loop("I CHOOSE YOU PIKACHU", "", "DO ")             #3
loop(" CHOOSE YOU PIKACHU", "I", "DO ")           #2
loop("CHOOSE YOU PIKACHU", "", "I DO ")             #3
loop("HOOSE YOU PIKACHU", "C", "I DO ")             #3
loop("OOSE YOU PIKACHU", "CH", "I DO ")             #3
loop("OSE YOU PIKACHU", "CHO", "I DO ")             #3
loop("SE YOU PIKACHU", "CHOO", "I DO ")             #3
loop("E YOU PIKACHU", "CHOOS", "I DO ")             #3
loop(" YOU PIKACHU", "CHOOSE", "I DO ")           #2
loop("YOU PIKACHU", "", "CHOOSE I DO ")             #3 
loop("OU PIKACHU", "Y", "CHOOSE I DO ")             #3
loop("U PIKACHU", "YO", "CHOOSE I DO ")             #3
loop(" PIKACHU", "YOU", "CHOOSE I DO ")           #2
loop("PIKACHU", "", "YOU CHOOSE I DO ")             #3
loop("IKACHU", "P", "YOU CHOOSE I DO ")             #3
loop("KACHU", "PI", "YOU CHOOSE I DO ")             #3
loop("ACHU", "PIK", "YOU CHOOSE I DO ")             #3
loop("CHU", "PIKA", "YOU CHOOSE I DO ")             #3
loop("HU", "PIKAC", "YOU CHOOSE I DO ")             #3
loop("U", "PIKACH", "YOU CHOOSE I DO ")             #3
loop("", "PIKACHU", "YOU CHOOSE I DO ")         #1
"PIKACHU YOU CHOOSE I DO "

I think it's important not to get stuck thinking about the problem in just one way. Try to do it different ways -

def rev(s, pos = 0):
  if pos >= len(s):
    return s                              #1
  elif s[pos] == " ":
    return rev(s[pos+1:]) + " " + s[0:pos]  #2
  else:
    return rev(s, pos + 1)                    #3

print(rev("DO I CHOOSE YOU PIKACHU"))

Evaluates as -

rev("DO I CHOOSE YOU PIKACHU", 0)                    #3
rev("DO I CHOOSE YOU PIKACHU", 1)                    #3
rev("DO I CHOOSE YOU PIKACHU", 2)                  #2
rev("I CHOOSE YOU PIKACHU", 0) + " " + "DO"          #3
rev("I CHOOSE YOU PIKACHU", 1) + " DO"             #2
rev("CHOOSE YOU PIKACHU", 0) + " " + "I" + " DO"     #3
rev("CHOOSE YOU PIKACHU", 1) + " I DO"               #3
rev("CHOOSE YOU PIKACHU", 2) + " I DO"               #3
rev("CHOOSE YOU PIKACHU", 3) + " I DO"               #3
rev("CHOOSE YOU PIKACHU", 4) + " I DO"               #3
rev("CHOOSE YOU PIKACHU", 5) + " I DO"               #3
rev("CHOOSE YOU PIKACHU", 6) + " I DO"             #2                
rev("YOU PIKACHU", 0) + " " + "CHOOSE" + " I DO"     #3
rev("YOU PIKACHU", 1) + " CHOOSE I DO"               #3
rev("YOU PIKACHU", 2) + " CHOOSE I DO"               #3
rev("PIKACHU", 0) + " " + "YOU" + " CHOOSE I DO"   #2
rev("PIKACHU", 1) + " YOU CHOOSE I DO"               #3
rev("PIKACHU", 2) + " YOU CHOOSE I DO"               #3
rev("PIKACHU", 3) + " YOU CHOOSE I DO"               #3
rev("PIKACHU", 4) + " YOU CHOOSE I DO"               #3
rev("PIKACHU", 5) + " YOU CHOOSE I DO"               #3
rev("PIKACHU", 6) + " YOU CHOOSE I DO"               #3
rev("PIKACHU", 7) + " YOU CHOOSE I DO"           #1
"PIKACHU" + " YOU CHOOSE I DO"
"PIKACHU YOU CHOOSE I DO"

There's infinite ways to express a program -

def find(s, char, ifmatch, nomatch):
  def loop(pos):
    if pos >= len(s):
      return nomatch()
    elif s[pos] == char:
      return ifmatch(pos)
    else:
      return loop(pos+1)
  return loop(0)

def cut(s, char, ifmatch, nomatch):
  return find \
    ( s
    , char
    , lambda pos: ifmatch(s[0:pos], s[pos+1:])
    , lambda: nomatch(s)
    )

def rev(s):
  return cut \
    ( s
    , " "
    , lambda left, right: rev(right) + " " + left
    , lambda last: last
    )

print(rev("DO I CHOOSE YOU PIKACHU"))

Evaluates as -

cut \
  ( "DO I CHOOSE YOU PIKACHU"s
  , " "
  , lambda left, right: rev(right) + " " + left
  , lambda last: last
  )

find \
  ( "DO I CHOOSE YOU PIKACHU"
  , " "
  , lambda pos: (lambda left, right: rev(right) + " " + left)("DO I CHOOSE YOU PIKACHU"[0:pos], "DO I CHOOSE YOU PIKACHU"[pos+1:])
  , lambda: (lambda last: last)("DO I CHOOSE YOU PIKACHU")
  )

loop(0)
loop(1)
loop(2)

(lambda left, right: rev(right) + " " + left) \
  ("DO I CHOOSE YOU PIKACHU"[0:2], "DO I CHOOSE YOU PIKACHU"[2+1:])

rev("I CHOOSE YOU PIKACHU") + " " + "DO"

# ...

"PIKACHU YOU CHOOSE I DO"

Reversing the order

6 Answers6