理解和可视化递归

问题描述

我提到的几个问题，在这里对递归，但我无法理解如何递归适用于这个特定的问题：递归程序得到一个字符串在Python所有字符组合：

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

全输出： http://pastebin.com/Lg3pLGtP

正如我在输出中所展示的，是怎么preFIX成为'AB'？

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

我试图想象的组合式的递归调用（preFIX + S [0]，S [1：]）。我是否理解对吗？

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

推荐答案

有两个递归调用在函数组合式（）。因而呼叫的路径是不是单行线，而是一个二叉树该叉。你们看到的是树的下半年。

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.

这篇关于理解和可视化递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！