递归 Recursion
关键词： 递归树(recursion tree)
全排列问题
问题描述：
用C++写一个函数, 如 Foo(const char *str), 打印出 str
的全排列,
如 abc 的全排列: abc, acb, bca, dac, cab, cba
thinking path:
进行全排列，对每种可能进行枚举，例如123，那么可以1与2互换，1与3互换，以及2与3互换。
问题稍微扩展为1234，1分别与2,3,4互换。总结规律就是对某个数，与其后面的数一一进行互换，得出该数在该位置的所有可能。
将该数向后“递进”一个位置，例如，1234,1与2互换后为，2134，再用同样的方法尝试2134中1后面的所有能与1互换的数字。
根据规律，可以列出递归伪代码:
allArrange(str,k,m) {
if k==m print;
for i=k to m {
swap(str,k,i); //k为第k个数
allArrange(str,k+1,m);
swap(str,k,i); //注意，因为递归有回溯的过程，所以需要把数字重新调换回来变为”初始“的排列。
}
}
贴出完整C代码
1 #include <stdio.h> 2 #include <string.h> 3 4 void swap(char* a, char* b) { 5 char tmp = *a; 6 *a = *b; 7 *b = tmp; 8 } 9 10 void allArrange(char* str, int currentIndex, int m) { 11 if (currentIndex == m) { 12 static int s_i = 1; 13 printf("currentIndex is %d, m is %d\n",currentIndex, m); 14 printf("the %2dth arrangement\t%s\n",s_i++, str); 15 } else { 16 for (int i = currentIndex; i <= m; i++) { 17 18 swap(str+currentIndex, str+i); 19 allArrange(str, currentIndex+1, m); 20 swap(str+currentIndex, str+i); 21 } 22 23 } 24 } 25 void arrange(char* str) { 26 allArrange(str, 0, strlen(str)-1); 27 } 28 int main() { 29 char str[] = "12345"; 30 arrange(str); 31 return 0; 32 }
递归的过程不易理解，可以画递归树(Recursion Tree)帮助理解。以"123"为例: