我在这里提到了几个有关递归的问题,但我无法理解递归如何解决这个特定问题:
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')
我已经让它打印这些值,以便我可以看到发生了什么。这是输出:
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
完整输出:http://pastebin.com/Lg3pLGtP
正如我在输出中所示,前缀如何变成“ab”?
I tried to visualize the recursive calls for the combi(prefix+s[0],s[1:]). Am I understanding it right?
![Visualization of Recursion](https://i.stack.imgur.com/6ci42.jpg)