文档章节

Go函数——递归

秋风醉了
 秋风醉了
发布于 2016/07/08 18:07
字数 933
阅读 57
收藏 0

Go函数——递归

递归一:为一组整数列求和

递归思想:如何为一组整数数列求和?按照通常命令式编程的思维,我们会采用循环,依次遍历列表中的每个元素进行累加,最终给出求和结果。这样的程序不难写,稍微具备一点编程经验的人在一分钟之内就能写出来。这次我们换个思维,如何用递归的方式求和?为此,我们不妨把问题简化一点,假设数列包含 N 个数,如果我们已经知道了后续 N – 1 个数的和,那么整个数列的和即为第一个数加上后续 N – 1 个数的和,依此类推,我们可以以同样的方式为 N – 1 个数继续求和,直到数列为空,显然,空数列的和为零。听起来复杂,事实上我们可以用一句话来总结:一个数列的和即为数列中的第一个数加上由后续数字组成的数列的和。 go代码表示如下,

package main

import (
	"fmt"
)

func main() {

	/* 创建切片,不指定元素个数*/
	numbers := []int{0, 1, 2, 3, 4, 5, 6, 7, 8}

	var result = sum(numbers)

	fmt.Println(result)
}

func sum(slice []int) int {

	if len(slice) == 0 {
		return 0
	} else {
		// slice[1:]  默认上限为 len(s)
		// 使用下标读取切片的元素
		return slice[0] + sum(slice[1:])
	}
}

递归二:求数列的最大值

递归思想:这个数列求和的例子并不是特别的,它代表了递归对于列表的一种普遍的处理方式,即对一个列表的操作,可转化为对第一个元素,及剩余列表的相同操作。比如我们可以用同样的方式求一个数列中的最大值。我们假设已经知道了除第一个元素外剩余数列的最大值,那么整个数列的最大值即为第一个元素和剩余数列最大值中的大者。这里需要注意的是对于一个空数列求最大值是没有意义的,所以我们需要向外抛出一个异常。当数列只包含一个元素时,最大值就为这个元素本身,这种情况是我们这个递归的边界条件。一个递归算法,必须要有这样一个边界条件,否则会一直递归下去,形成死循环。 go代码表示如下,

package main

import (
	"fmt"
)

func main() {

	defer func() { // 必须要先声明defer,否则不能捕获到panic异常
		if err := recover(); err != nil {
			fmt.Println(err) // 这里的err其实就是panic传入的内容
		}
	}()

	/* 创建切片,不指定元素个数*/
	numbers := []int{0, 1, 2, 3, 4, 5, 6, 7, 8}

	var res = max(numbers)

	fmt.Println(res)

	empty_slice := make([]int, 0, 0)

	var res2 = max(empty_slice)

	fmt.Println(res2)

	fmt.Println("end")

}

func max(slice []int) int {

	if len(slice) == 0 || slice == nil {
		panic("数列为空")
	}

	if len(slice) == 1 {
		return slice[0]
	} else if slice[0] > max(slice[1:]) {
		return slice[0]
	} else {
		return max(slice[1:])
	}
}

递归三:反转字符串

递归思想:让我们再看一个例子:如何反转一个字符串?比如给定一个字符串"abcd",经过反转之后变为 "dcba"。同样的,我们可以做一个大胆的假设,假设后续字符串已经反转过来,那么接上第一个字符,整个字符串就反转过来了。对于一个只有一个字符的字符串,不需要反转,这是我们这个递归算法的边界条件。 go代码表示如下,

package main

import (
	"fmt"
)

func main() {
	str := "hello"
	var res = reverse(str)
	fmt.Println(res)
}

func reverse(str string) string {
	if len(str) == 1 {
		return str
	} else {
		rs := []rune(str)
		return reverse(string(rs[1:])) + string(rs[0:1])
	}
}

=========END=========

© 著作权归作者所有

共有 人打赏支持
秋风醉了
粉丝 239
博文 572
码字总数 416654
作品 0
朝阳
程序员
私信 提问
day14(函数的基础2)

函数参数—必选参数 必选参数须以正确的顺序传入函数。调用时的数量必须和声明时的一样。 注意:必选参数必须和声明时的数量和位置一致,不然会报错。 函数参数—默认参数 调用函数时,缺少参...

冰封心动
2017/11/09
0
0
python算法-1.简介/2.选择排序

第一章、 算法简介 一些常见的大O运行时间 》 ,也叫对数时间,这样的算法包括二分查找。 》 ,也叫线性时间,这样的算法包括简单查找。 》 ,这样的算法包括第4章将介绍的快速排序——一种速...

时间之友
2017/12/15
0
0
Node中的两种遍历方式-深度优先和广度优先(附Node删除文件例子进行详解)

树的基本概念 树(Tree)是 个结点的有限集, 为 时,称为空树,在任意一棵非空树中有且仅有一个特定的被称为根(Root)的结点,当 大于 时,其余结点可分为 个互不相交的有限集 、、、,其中...

09/14
0
0
《C Primer Plus》读书笔记——递归

递归的原理 一个函数调用其本身,此调用过程为递归(recursion)。 递归的使用 举个栗子: 输出如下: 递归的基本原理 每级递归都使用其私有变量(如例子中的n) 每次函数调用都返回前一级(...

cugwyman
2017/02/04
0
0
Java IO流(一)

IO(Input Output)流的概述 下面给出IO流的基本概述,这样可以对IO流有一个宏观上的基本了解。 IO流用来处理设备之间的数据传输。 Java对数据的操作是通过流(系统资源)的方式。 Java用于操作流...

yerenyuan_pku
2017/10/13
0
0

没有更多内容

加载失败,请刷新页面

加载更多

docker搞个wordpress

1.先把wordpress的镜像下载下来 docker pull wordpress 2.下载mysql docker pull mysql:lastest 3.启动mysql docker run --name blog -e root -d mysql:5.7 docker run --name some-mysql -e......

无极之岚
13分钟前
0
0
【宇润日常疯测-005】PHP 中的 clone 和 new 性能比较

clone和new本不应该放在一起比较,它们的作用是不同的。但可能有一些场景下,可以用clone也可以用new,那么这时候我们选哪个呢? 我编写了两个测试,第一个是声明一个空类,第二个是带构造方...

宇润
13分钟前
0
1
点击按钮弹出类似IOS 底部 dialog

implementation 'com.baoyz.actionsheet:library:1.1.7' 然后设置按钮点击监听,,调用下列代码即可 ActionSheet.createBuilder(this, getSupportFragmentManager()) ......

lanyu96
17分钟前
1
0
专访阿里云专有云马劲,一个理性的理想主义者

“我的故事都是和团队技术相关的,自己还真没有什么引人入胜的故事。”当马劲被问到能不能多分享些个人经历故事时他笑着说,我们就干脆怀着好奇聊了聊他和阿里云专有云一路走来的故事。 马劲...

阿里云官方博客
49分钟前
1
0
java环形缓冲区

import java.util.ArrayList;import java.util.List;/** * * 环形缓冲区<br/> * 一. 写数据:<br/> * 1. push: 当数据已写满时返回false,否则可以正常写入返回true<br/>......

whoisliang
今天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部