递归学习

发表于 阅读次数：

递归、循环的区别：

  • 循环：循环嵌套层数由代码结构决定，维度不可变。

  • 递归：能产生循环嵌套，可以扩展循环层数。

举例：遍历所有组合—— C6取3

[1,2,3] [1,2,4] [1,2,5] [1,2,6] [1,3,4] [1,3,5] [1,3,6] [1,4,5] [1,4,6] [1,5,6]
[2,3,4] [2,3,5] [2,3,6] [2,4,5] [2,4,6] [2,5,6]
[3,4,5] [3,4,6] [3,5,6]
[4,5,6]

  • 循环：

    1
    2
    3
    4
    5
    6
    7
    8
    for(int i=1;i<=4;i++)
    	for(int j=i;j<=5;j++)
    		for(int k=j;k<=6;k++){
    			temp.set(0, i);
    			temp.set(1, j);
    			temp.set(2, k);
    			rtn.add(temp);
    		}

    每个数组有三个元素，用三层for循环。

  • 递归：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    //计算C6取3
    //遍历数字范围：start=1，end=6
    //小容器容量为3：totle=3
    //小容器内计数器从零开始计数：count=0
    //综上，调用solve(0,3,1,6);
    public void solve(int count, int totle, int start, int end) {
    	if (count == totle) {
    		rtn.add(temp);
    		return;
    	}
    	for (int i = start; i <= end; i++) {
    		temp.set(count, i);
    		solve(count + 1, totle, i + 1, end);
    	}
    }

如果遍历C6取4呢？

  • 循环：加一层for循环

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    for(int i=1;i<=3;i++)
    	for(int j=i;j<=4;j++)
    		for(int k=j;k<=5;k++)
    			for(int l=k;l<=6;l++){
    				temp.set(0, i);
    				temp.set(1, j);
    				temp.set(2, k);
    				temp.set(3, l);
    				rtn.add(temp);
    			}

  • 递归：只需将入口参数totle由3修改为4即可：
    solve(0,4,1,6);

更一般地，如果遍历Cn取k

  • 递归：n和k为变量，递归依然只需更改入口参数：
    solve(0,k ,1, n);
  • 循环：呵呵