【算法】递归思想

柔光的暖阳◎ 2023-10-10 09:36 73阅读 0赞

给定一个字符串（该字符串没有相同的字母），使用递归的方式打印出这个字符串所包含字母的所有组合方式

package test1;
    
    public class num {
        public static void main(String[] args) {
            char[] c= {'a','b','c','d'};
            f(c,0);
        }
        
        /* c为待递归数组，先确定第一个字符，再确定第二个...b为所有已确定字符位的后一个字符位 */
        static void f(char c[],int b) {
            if(b==c.length-1) {
                /* 如果b已经是最后一个字符，所有字符已经确定 */
                System.out.println(c);//打印字符串，结束循环。
            }else {
                /* 如果b不是最后一个字符 */
                for(int i=b;i<c.length;i++) {
                    swap(c,b,i);//b和自己以及和之后的字符交换，使未确定每一个字符都有在b位确定的机会，【已经确定字符】【b】【剩下的字符】——》【已经确定字符】【i】【剩下的字符】
                    f(c,b+1);//确定下一位
                    swap(c,i,b);//因为i++后的i位还要和原来的b位交换，保证每一个字符都有在b位确定的机会，【已经确定字符】【i】【剩下的字符】——》【已经确定字符】【b】【剩下的字符】
                }
            }
        }
        
        /* 交换数组中两个字符位置 */
        static void swap(char c[],int a,int b) {
            char t=c[a];
            c[a]=c[b];
            c[b]=t;
        }
    }

递归的思想：

1.递归函数是上司，上司完成自己要做的事，然后交给 下属 干剩下的事

2.递归函数既是长官，又是下属，干完自己分内的事，剩下交给属下干

3.递归函数最后由最后的下属完成

例如：

1。f是最大上司，手上有为（0~L）位字符数组c，f的任务是从c里选一个字符确定在b（b=0）位，然后把字符串c剩下（1~L）的位交给下属确定，告诉下属b位和b位前的字符已经确定

2。下属拿到字符串c后，再选b位以及b位之后的一个字符确定在b位（因为b位之前的字符已经被上司确定了），然后剩下（（b+1）~L）的位交给下属确定，告诉下属b位和b位前的字符已经确定

3。最后的下属要确定L位，由于之前的字符都已经确定，L位没得选，所以这名下属打印这个字符串，而且不继续给自己的下属任务。

转载于:https://www.cnblogs.com/LPworld/p/11520695.html