递归该怎么写（二）

对于简单的递归（可以写出数学表达式的递归），我们已经熟练掌握，但是对于有些递归我们有时候无从下手。这时候我们需要将抽象的问题数学化，或者能表达出来。

 （本节需要掌握： 熟悉递归函数的返回是一个什么？？？）

例1：字符串的全排列问题（剑指offer）

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

首先我们考虑该问题是否是可以用相同方法解决？ 对于abcd例子

① a b c d 的排列我们首先用表达式表达  Perm（a b c d）  这个表示对 abcd全排列

② 然后发现把abcd 全排列就可以转化为     把 a打头 对 bcd 全排列Perm（b c d）     b打头 对 acd 全排列Perm（a c d）     

c打头 对 abd 全排列Perm（a b d）      d打头 对 abc 全排列Perm（a b c）

③ 这个就不是很简单的递归了，这需要我们加入一些条件（循环），来让它执行递归过程。  其实第二个过程就是一个循环的过程

def prem(abcd)：
    for i in abcd：
　　    i + prem(没有i的字符串)    我们可以保留的结果



这里我们假设 prem返回的就是 一些字符的排列组合的结果。

比如a + prem(cd)   就相当于 a + [cd, dc]  ----> acd  adc

注意   ：    （这个理解了就很简单了）

④ 这时候我们还有十分重要的一步（递归出口在哪呢？？？）    我们将问题一步步分解，发现 例如  abc排好了  剩下d 一个了，那就不需要执行prem了。

出口就是： 当为一个字符时结束

def Permutation(ss):
        # write code here
        result = []
        if not ss:
            return []
        if len(ss) ==1:   #出口
            return [ss]
        for i in range(len(ss)):          #分别固定每一个开头
            temp = Permutation(ss[:i] + ss[i+1:])        #排列剩下的， 假设返回一个列表结果
            for j in temp:
                result.append(ss[i] + j)     #保存结果，这部分很难理解  只需要理解第三步就很好理解了
        return list(set(result))

 

例2：