Understanding and visualizing recursion

Question

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

carlsborg · Accepted Answer · 2022-05-20 08:27:52Z

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!)

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")

edited May 20, 2022 at 8:27

answered May 24, 2014 at 21:51

carlsborg

3,00923 silver badges22 bronze badges

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

1 Comment

Bharat Over a year ago

Thanks. Looks interesting. I'll try it out.

Amber · Accepted Answer · 2012-02-07 03:40:44Z

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.

answered Feb 7, 2012 at 3:40

Amber

531k89 gold badges643 silver badges558 bronze badges

7 Comments

Bharat Over a year ago

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.

kevintodisco Over a year ago

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).

Amber Over a year ago

@RBK: It's the call for combi('a', 'c') from combi('a','bc') that's creating the second prefix='a'.

Bharat Over a year ago

@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 Over a year ago

@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 · Accepted Answer · 2012-02-07 18:26:50Z

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

answered Feb 7, 2012 at 18:26

Bharat

3,0302 gold badges41 silver badges57 bronze badges

Comments

Bishal Sarang · Accepted Answer · 2020-02-27 14:50:08Z

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:
Also, a recursion tree saved as png with return value:

Check out more examples here.

Collectives™ on Stack Overflow

Understanding and visualizing recursion

4 Answers 4

1 Comment

7 Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

1 Comment

7 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related