实践--如何写递归?

实践--如何写递归?

  • 2018-02-21

递归书写方法

  1. 严格定义递归函数作用,包括参数,返回值,side effect
  2. 先一般再特殊
  3. 每次递归必须缩小问题规模
  4. 每次问题规模缩小程度必须为1

总之递归就是”装傻”的把原始的思路表现出来,不需要关心具体过程,只需要不停的缩小问题规模,然后答案自然就会被计算出来.

举例

斐波那契数列

问题描述求出斐波那契数列第n位数值,也就是f(n).
按照题目意图,递归函数为 f(n),其中n为要求出值的索引位置.

1
2
func fibonacci(n int) int {
}

先考虑一般情况,且每一次递归都要缩小规模,对于斐波那契数列其f(n) = f(n-1)+f(n-2),那么就可以写出下列函数

1
2
3
func fibonacci(n int) int {
	return fibonacci(n-1) + fibonacci(n-2)
}

在考虑特殊情况,一般特殊情况即递归的结束条件,对于斐波那契数列为第一位以及第二位为1,也就是n小于3返回1,到此完成了该题.

1
2
3
4
5
6
func fibonacci(n int) int {
	if n < 3 {
		return 1
	}
	return fibonacci(n-1) + fibonacci(n-2)
}

汉诺塔问题

　从左到右有A、B、C三根柱子，其中A柱子上面有从小叠到大的n个圆盘，现要求将A柱子上的圆盘移到C柱子上去，期间只有一个原则：一次只能移到一个盘子且大盘子不能在小盘子上面，求移动的步骤和移动的次数

首先要明确当n>2的时候,必须借助B柱子才能实现从A到C,具体怎么移动不需要关心.
根据题意定义出函数

1
2
3
4
5
/**
 * 将n个盘子从A上借助B移动到C
 **/
func hanoi(n int, A string, B string, C string){
}

那么对于n个柱子从A到C上,自然先把n-1个柱子从A到B上,然后再把第n个柱子移动到C上.

1
2
3
4
5
func hanoi(n int, A string, B string, C string) {
	hanoi(n-1, A, C, B)
	fmt.Println("从" + A + "上移动" + (strconv.Itoa(n - 1)) + "借助" + B + "到" + C)
	count++
}

那么移动完第n个柱子后,接下来的问题规模变成了把n-1个柱子从B移动到C上,自然在上述操作最后加上这步操作

1
2
3
4
5
6
7
func hanoi(n int, A string, B string, C string) {
	hanoi(n-1, A, C, B)
	fmt.Println("从" + A + "上移动" + (strconv.Itoa(n - 1)) + "借助" + B + "到" + C)
	count++
     // 把n-1个柱子从B移动到C上,
	hanoi(n-1, B, A, C)
}

考虑特殊情况,当只有一个盘子的时候,也就是n为1,那么直接移动即可.

1
2
3
4
5
6
7
8
9
10
11
func hanoi(n int, A string, B string, C string) {
	if n == 1 {
		count++
		fmt.Println("从" + A + "上移动" + (strconv.Itoa(n - 1)) + "到" + C)
		return
	}
	hanoi(n-1, A, C, B)
	fmt.Println("从" + A + "上移动" + (strconv.Itoa(n - 1)) + "借助" + B + "到" + C)
	count++
	hanoi(n-1, B, A, C)
}

整个流程结束,我们并没有关心具体的移动是怎么进行的,只需要知道大概步骤,不停地缩小问题规模就可以完成.

二路归并排序

归并排序是分治思想的体现,能分治解决的问题绝大多数可以递归解决,其实递归不断缩小问题规模本身也是分治思想.
那么先定义归并函数对一个数组排序.

1
2
func mergesort(arr []int) []int {
}

然后策略,归并是不停地拆分数组,当数组足够小且方便排序的时候为止,然后把问题转换成有序数组的合并.这里数组拆分为只有一个元素为止,那么其必然有序.
那么思路,拆分数组为两个数组,然后合并

1
2
3
4
5
6
7
8
9
func mergesort(arr []int) []int {
	arrLen := len(arr)
	//拆分arr1
	arr1 := mergesort(arr[:arrLen/2])
	//拆分arr2
	arr2 := mergesort(arr[arrLen/2:])
	// merge arr1 arr2,是两个有序集合的合并.
	return merge(arr1, arr2)
}

特殊情况,当数组长度为1的时候,即此时是有序的,直接返回合并即可

1
2
3
4
5
6
7
8
9
10
11
12
func mergesort(arr []int) []int {
	arrLen := len(arr)
	if arrLen == 1 {
		return arr
	}
	//拆分arr1
	arr1 := mergesort(arr[:arrLen/2])
	//拆分arr2
	arr2 := mergesort(arr[arrLen/2:])
	// merge arr1 arr2,两个有序集合的合并.
	return merge(arr1, arr2)
}

那么归并排序就完成了,还剩下一个问题func merge(arr1 []int, arr2 []int) []int两个有序数组合并成一个有序数组,也就是归并.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func merge(arr1 []int, arr2 []int) []int {
	var newArr []int
	indexArr2 := 0
	indexArr1 := 0

	for ; indexArr1 < len(arr1) && indexArr2 < len(arr2); {
		if arr1[indexArr1] > arr2[indexArr2] {
			newArr = append(newArr, arr2[indexArr2])
			indexArr2++
		} else {
			newArr = append(newArr, arr1[indexArr1])
			indexArr1++
		}
	}
	// 遍历完情况
	if len(arr2) > indexArr2 {
		newArr = append(newArr, arr2[indexArr2:]...)
	}
	if len(arr1) > indexArr1 {
		newArr = append(newArr, arr1[indexArr1:]...)
	}
	return newArr
}

全排列问题

    如下的10个格子
       +--+--+--+
       |  |  |  |
    +--+--+--+--+
    |  |  |  |  |
    +--+--+--+--+
    |  |  |  |
    +--+--+--+
    （如果显示有问题，也可以参看下图）
    填入0~9的数字。要求：连续的两个数字不能相邻。
    （左右、上下、对角都算相邻）
    一共有多少种可能的填数方案？
    请填写表示方案数目的整数。
    注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。

这是2016蓝桥杯B组一道题,当时年少无知没做出来(笑哭)……
思路暴力方法最简单,每个数都在方格试试….
根据题意定义函数,在数组位置填充数组,为了简单我把数组直接用初始值声明好了,其中-5代表不用填写的两个格子.

1
2
3
4
5
6
7
8
var arr = [3][4]int{
	{-5,-2,-2,-2},
	{-2,-2,-2,-2},
	{-2,-2,-2,-5},
}

func fillGrid( y int, x int) {
}

然后循环0-9,一个一个的试试.其中visit数组记录该元素是否已经填充过.check函数则检查条件上下左右以及对角线是否相邻,很简单的函数,不贴代码了.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func fillGrid( y int, x int) {
	for i := 0; i <= 9; i++ {
		// check
		if visit[i] != 0 || !check(y, x, i) {
			continue
		}
		//填入值
		arr[y][x] = i
       //标记该值已访问
		visit[i] = 1
		//下一个坑填入
		if x == 3 {
			fillGrid( y+1, 0)
		} else {
			fillGrid( y, x+1)
		}
        //恢复数据
		arr[y][x] = -2
		visit[i] = 0
	}
}

特殊情况考虑,也就是递归的结束条件,当遍历到最后一个格子arr[2][3]时则结束.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
func fillGrid( y int, x int) {
	if y == 2 && x == 3 {
		total++
		return
	}
	for i := 0; i <= 9; i++ {
		// check
		if visit[i] != 0 || !check(y, x, i) {
			continue
		}
		//填入值
		arr[y][x] = i
            //标记该值已访问
		visit[i] = 1
		//下一个坑填入
		if x == 3 {
			fillGrid( y+1, 0)
		} else {
			fillGrid( y, x+1)
		}
           //恢复数据
		arr[y][x] = -2
		visit[i] = 0
	}
}

到此完成遍历.直接从第二个格子开始填值fillGrid(0,1)即可得到答案1580.

备注

1.实例写法只是怎么便于理解怎么写,不涉及各种优化,比如归并可以使用一个数组逻辑上当成多个数组使用,这样只会带来额外的理解成本,保证先写出来,思路是对的,然后再考虑优化.

2.代码都是golang编写,最近才开始学习的go,使用不当之处还请指出.

Java--StringBuilder,StringBuffer,StringJoiner
(转)Java--栈与队列