Recursion Python

Question

def removedups(word):
  if len(word)<=1:
    return word
  else:
    if word[0]==word[1]:
      return removedups(word[1:])
    else:
      return word[0]+removedups(word[1:])

print(removedups('aabbcc'))

I dont get how the recursion works for this case. My knowledge so far is:

1) it skips the base test

2) goes to the recursion call and returns 'abbcc', and then it starts over again:

3) the if statement in recursion call is false so you disregard it

4) The else statement is where i get confused when it says return word[0] +removedups(word[1:]). Does it go the if statement and checks the word('bbcc')

Btw, that first else clause can be removed, and the second if can become one elif, and moved back an indentation with the last else. Proper syntax ;) — kingstante
– kingstante, Commented Jan 31, 2017 at 0:42

Bleh · Accepted Answer · 2017-01-31 00:34:14Z

1

return word[0]+removedups(word[1:])

word[0]+removedups(word[1:]) is returned only when the execution of removedups(word[1:]) is complete.

removedups('bbcc') returns 'bc'

So removedups('abbcc') returns 'a' + 'bc' i.e. 'abc'

answered Jan 31, 2017 at 0:34

Bleh

4513 silver badges15 bronze badges

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

2 Comments

Chris Over a year ago

Hi! if u dont mind can you explain in a bit more detailed pls

Bleh Over a year ago

removedups('aabbcc')  = removedups('abbcc') = 'a' + removedups('bbcc') removedups('bbcc') = removedups('bcc') = 'b' + removedups('cc') removedups('cc') = removedups('c') = 'c'

Scott Hunter · Accepted Answer · 2017-01-31 00:31:40Z

1

You get to that last else if the list has at least 2 elements and the first 2 aren't the same. This means that the first element is not a duplicate, and thus needs to appear in the result. But there may be other duplicates in the rest of the list. Thus, the answer is to add back that first element onto what you get by removing any duplicates from the rest of the list: word[0]+removedups(word[1:]).

answered Jan 31, 2017 at 0:31

Scott Hunter

50k12 gold badges65 silver badges107 bronze badges

Comments

Mamun Rashid · Accepted Answer · 2019-11-28 15:50:58Z

1

The best way to visualize a recursion is by drawing a recursion tree.

 removedups("aabbcc") --> removedups("abbcc") --> "a" + removedups("bbcc") --> removedups("bcc") --> "b" + removedups("cc")  --> removeups("c") --> "c"

During traceback:

  removedups("cc") = removeups("c") = "c"
  => "b" + removedups("cc") = "bc"
  removedups("bbcc") = removedups("bcc") = "bc"
  => "a" + removedups("bbcc") = "abc"
  removedups("aabbcc") = removedups("abbcc") = "abc"

answered Nov 28, 2019 at 15:50

Mamun Rashid

434 bronze badges

Comments

Varunnuevothoughts · Accepted Answer · 2017-05-24 13:07:26Z

0

The last else condition and base case are responsible for producing 'abc' result.Whereas else: if word[0]==word[1]: is removing duplicate elements.

removedups('aabbcc') =>removedups('abbcc')

removedups('abbcc') =>'a' + removedups('bbcc')

'a' + removedups('bbcc')  =>'a'+ removedups('bcc')

'a' removedups('bcc') =>'ab' + removedups('cc')

'ab' + removedups('cc') => 'ab' + removedups('c')

'ab' + removedups('c') => 'abc'

answered May 24, 2017 at 13:07

Varunnuevothoughts

711 silver badge2 bronze badges

Comments

bterwijn · Accepted Answer · 2025-03-08 12:24:59Z

0

You can you package invocation_tree to visualize program execution which is especially helpful with recursion.

import invocation_tree as ivt # see above link for install instruction

def removedups(word):
  if len(word)<=1:
    return word
  else:
    if word[0]==word[1]:
      return removedups(word[1:])
    else:
      return word[0]+removedups(word[1:])

tree = ivt.blocking()
result = tree(removedups, 'aabbcc') # show invocation tree of removedups('aabbcc')
print(result)

That after pressing <Enter> a number of times to step through the program, results in:

I hope this visualization will help you with program understanding.

Full disclosure: I am the developer of invocation_tree.

edited Mar 8 at 12:24

answered Feb 23 at 18:14

bterwijn

1

Collectives™ on Stack Overflow

Recursion Python

5 Answers 5

2 Comments

Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

2 Comments

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related