7

I referred to several questions here about recursion but I am not able to understand how recursion works for this particular problem: Recursive program to get all combination of characters in a string in Python:

st= []
def combi(prefix, s):
    if len(s)==0: return 
    else:
        st.append(prefix+s[0])        

        ''' printing values so that I can see what happens at each stage '''
        print "s[0]=",s[0]
        print "s[1:]=",s[1:]
        print "prefix=",prefix
        print "prefix+s[0]=",prefix+s[0]
        print "st=",st

        combi(prefix+s[0],s[1:])
        combi(prefix,s[1:])
        return st

print combi("",'abc')

I've made it print the values so that I can see what's happening. This is the output:

s[0]= a
s[1:]= bc
prefix= 
prefix+s[0]= a
st= ['a']
s[0]= b
s[1:]= c
prefix= a
prefix+s[0]= ab
st= ['a', 'ab']
s[0]= c
s[1:]= 
prefix= ab
prefix+s[0]= abc
st= ['a', 'ab', 'abc']
s[0]= c
s[1:]= 
prefix= a  ----> How did prefix become 'a' here. Shouldn't it be 'abc' ? 
prefix+s[0]= ac
st= ['a', 'ab', 'abc', 'ac']
.........
.........
['a', 'ab', 'abc', 'ac', 'b', 'bc', 'c'] # final output

Full output: http://pastebin.com/Lg3pLGtP

As I've shown in the output, how did prefix become 'ab'?

I tried to visualize the recursive calls for the combi(prefix+s[0],s[1:]). Am I understanding it right? Visualization of Recursion

4 Answers 4

7

From this excellent browser based python recursion visualizer:

Paste your code as:

st= []
def combi(prefix, s):
    if len(s)==0: 
        return 
    else:
        st.append(prefix+s[0])     
        combi(prefix+s[0],s[1:])
        combi(prefix,s[1:])
        return st

And it generates this diagram which you can step through one call at a time. (The truly wonderful thing is the python is executed in your browser using web assembly!)

enter image description here

You could also look at a stand alone python module for that

rcviz output

Generated with:

from rcviz import callgraph, viz
st= []
@viz
def combi(prefix, s):
    if len(s)==0: 
        return 
    else:
        st.append(prefix+s[0])     
        combi.track(st = st) #track st in rcviz 
        combi(prefix+s[0],s[1:])
        combi(prefix,s[1:])
        return st

print combi("",'abc')
callgraph.render("combi.png")
1
  • Thanks. Looks interesting. I'll try it out.
    – Bharat
    May 25, 2014 at 4:08
2

There are two recursive calls to combi() in the function. Thus the path of calls is not a single line, but rather a binary tree that forks. What you are seeing is the second half of the tree.

7
  • I thought the 2nd recursive call i.e combi(prefix,s[1:]) would start off as combi('','bc') and go though the same process forming b,bc. Here at the last step s[0] is 'c' and when recursing out prefix+s[0] becomes ''+c = c if I understand it right? Btw, I've added a pastbin link of the complete output to the question.
    – Bharat
    Feb 7, 2012 at 3:48
  • If you're familiar with depth-first search, it's how the tree Amber mentions is being traversed (or generated, depending on how you want to look at it). Feb 7, 2012 at 3:56
  • @RBK: It's the call for combi('a', 'c') from combi('a','bc') that's creating the second prefix='a'.
    – Amber
    Feb 7, 2012 at 3:59
  • @ktodisco , Yes I know Depth first traversal. I think the connection with recursion in general would be that DFS uses a stack.. I will try to visualize it on paper & see... I am still not able to understand how the backtracking works exactly.
    – Bharat
    Feb 7, 2012 at 4:05
  • @Amber, prefix+s[0] is passed as the 1st argument to combi, doesn't prefix now become 'ab' after the call to combi('a','bc') ? How does it remain 'a' ?
    – Bharat
    Feb 7, 2012 at 4:11
2

I drew the recursion tree. By Depth First Traversal, the final output is got at the last node. This visualization helps understand what's happening.

Recursion Tree

1

I've written a python package called recursion-visualiser which helps to draw a recursion tree for any arbitary recursive function. You have to simply add a decorator and boom you have nice animation and recursion tree saved as gif and png.

from visualiser.visualiser import Visualiser as vs

st= []
@vs(show_argument_name=False, node_properties_kwargs={"shape":"record", 
"color":"#f57542", "style":"filled", "fillcolor":"grey"})
def combi(prefix, s):
    if len(s) == 0:
        return " "
    else:
        st.append(prefix + s[0])
        combi(prefix=prefix + s[0], s=s[1:])
        combi(prefix=prefix, s=s[1:])
        return st

print(combi(prefix="",s='abc'))
vs.make_animation("combinations.gif", delay=3)

Here is the output gif: combinations.gif
Also, a recursion tree saved as png with return value: combinations.png

Check out more examples here.

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.