算法回顾--如何写递归?


递归书写方法

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

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

举例

斐波那契数列

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

func fibonacci(n int) int {
}

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

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

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

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,具体怎么移动不需要关心. 根据题意定义出函数

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

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

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上,自然在上述操作最后加上这步操作

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,那么直接移动即可.

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)
}

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

二路归并排序

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

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

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

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的时候,即此时是有序的,直接返回合并即可

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两个有序数组合并成一个有序数组,也就是归并.

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代表不用填写的两个格子.

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函数则检查条件上下左右以及对角线是否相邻,很简单的函数,不贴代码了.

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]时则结束.

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,使用不当之处还请指出.

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏静晴轩

JavaScript 字符串实用常操纪要

JavaScript 字符串用于存储和处理文本。因此在编写 JS 代码之时她总如影随形,在你处理用户的输入数据的时候,在读取或设置 DOM 对象的属性时,在操作...

3947
来自专栏Python小屋

Python花式编程案例集锦(9):sorted()函数中消失的cmp参数

明天开启全国巡讲Python模式,连续8场20天讲课,外加路上来回大约16天,这个假期有的忙了。所以接下来的一段时间里不一定能像以前更新的那么频繁,我尽量。

1023
来自专栏开发技术

排序之希尔排序(shell sort)

本篇博客是在伍迷兄的博客基础上进行的,其博客地址点击就可以进去,里面好博客很多,我的排序算法都来自于此;一些数据结构方面的概念我就不多阐述了,伍迷兄的博客中都...

1323
来自专栏大数据杂谈

从 Zero 到 Hero ,一文掌握 Python

2039
来自专栏数据小魔方

左右用R右手Python系列——字符串格式化输出

学习Python不到一个月,虽然学的很渣,但是还是想通过这种途径分享自己的学习心得,毕竟当初学习R语言也是这么走过来的。 今天是R语言与Python综合系列的第...

4366
来自专栏owent

VC和GCC成员函数指针实现的研究(三)

因为是兼容虚继承和非虚继承的,所以赋值的部分的汇编是一样的。这里就不贴了。关键在于执行期它是怎么找到虚基类的。请往下看:

901
来自专栏软件开发 -- 分享 互助 成长

希尔排序

1、希尔排序介绍 希尔排序是对直接插入排序算法的一种改进,当记录较少或者记录本身基本有序的时候直接插入排序的优势非常明显,所以希尔排序就是通过人为的创造这两个条...

1978
来自专栏java一日一条

使用 Java 8 Optional 的正确姿势

我们知道 Java 8 增加了一些很有用的 API, 其中一个就是 Optional. 如果对它不稍假探索, 只是轻描淡写的认为它可以优雅的解决 NullPoi...

1491
来自专栏海天一树

小朋友学C语言(25):两数交换

(一) #include <stdio.h> int main() { int a = 10; int b = 5; printf("B...

3046
来自专栏Leetcode名企之路

【Leetcode】58. 最后一个单词的长度

这个题比较水,主要是注意一下前后有空格这种情况。 如下代码用preLong记录截止到当前字符最后一个单词的长度.

1012

扫码关注云+社区

领取腾讯云代金券