文档章节

Go函数——递归

秋风醉了
 秋风醉了
发布于 2016/07/08 18:07
字数 933
阅读 37
收藏 0
点赞 0
评论 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=========

© 著作权归作者所有

共有 人打赏支持
秋风醉了
粉丝 229
博文 577
码字总数 407134
作品 0
朝阳
程序员
day14(函数的基础2)

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

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

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

时间之友
2017/12/15
0
0
递归(一)

这次先不谈数据结构,来聊聊算法设计中非常常用的一个东西——递归。 让我们用个大家非常熟悉的东西——等差数列。 打开高中课本,等差数列是这样定义的:从第二项开始,每一项与前一项的差都...

BillAlen
2016/10/26
0
0
递归入门--阶乘函数java实现

递归函数里面一般都是要有if开头的语句,也就是递归的出口。 递归的思想就是把大的问题分割成一个个相似的小问题来解决。 编写递归代码是最重要的有以下三点: 1.递归总有一个最简单的情况—...

Amui
2015/10/01
17
0
Java IO流(一)

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

yerenyuan_pku
2017/10/13
0
0
【Python学习笔记】递归函数

★特殊的一种函数——递归函数 通常,函数是靠调用其他函数完成自己的功能的,但是还存在一种调用方式是:函数调用它自身,这样的函数称为递归函数 递归函数是利用'栈'实现的,递归函数的优点...

Master_Li
2016/09/13
18
0
时间复杂度和空房间复杂度

一、时间复杂度:(注意:不是指程序运行时间) 1定义:一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数,用T(n)表示,若有某个辅助函数f(n),使得当n趋近于无穷大时,T(n)/...

qq_38646470
2017/12/09
0
0
(优酷2014年笔试题 )数组重新组合求最小值

zhagoodwell 查昊昊 优酷2014年笔试题 题目:含有n个元素的整型数组,将这个n个元素重新组合,求出最小的数,如{321,3,32},最小的数为 321323 下面的代码 复杂度为 o(n²);因为用了选择排序...

zhagoodwell
2017/02/09
0
0
JavaScript 学习笔记2

第三章 基本概念 1.注释 单行:// 多行:/adsfkdldnfknksmd/ 2.严格模式 顶部添加“use strict”; 3.关键字和保留字 4.变量 松散类型,可以保存任何类型的数据 var操作符定义的变量将成为定义...

candy-chocolate
2016/10/31
4
0
STL系列之十 全排列(百度迅雷笔试题)

全排列在笔试面试中很热门,因为它难度适中,既可以考察递归实现,又能进一步考察非递归的实现,便于区分出考生的水平。所以在百度和迅雷的校园招聘以及程序员和软件设计师的考试中都考到了,...

彭博
2012/04/12
379
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

大数据基础知识,大数据学习,涉及的知识点

一、什么是大数据 一种规模大到在获取、存储、管理、分析方面大大超出了传统数据库软件工具能力范围的数据集合,具有海量的数据规模、快速的数据流 转、多样的数据类型和价值密度低四大特征。...

董黎明
12分钟前
0
0
Linux CentOS 7上安装极点五笔

话说几天前在新买的惠普笔记本上成功地安装了Linux CentOS 7操作系统、Nvidia Quandro P600驱动程序及X Window,并在VMware下安装Red Hat教学环境,彻底跳出Windows的苦海,但仍然有一件事不...

大别阿郎
25分钟前
0
0
2018年7月20日集群课程

一、集群介绍 集群,简单地说是指一组(若干个)相互独立的计算机,利用高速通信网络组成一个较大的计算机服务系统,每个集群节点(即集群中的每台计算机)都是运行各自服务的独立服务器。 ...

人在艹木中
27分钟前
0
0
spark开发机中调试snappy

目的 在Idea中的点击运行,使spark可以直接读取snappy 自己编译hadoop,以支持snappy的压缩。 自己编译的目的就是要得到支持snappy文件读写的动态链接库。如果可以在网上下载,可以跳过自行编...

benny周
45分钟前
0
0
centos7 安装docker

1,查看系统版本 cat /etc/redhat-release 2,安装gcc yum -y install gccyum -y install gcc-c++ 3,卸载旧版本 yum remove docker \ docker-client \ ......

暗中观察
46分钟前
0
0
rabbitmq学习记录(七)交换机Exchange-topic

实现功能:一条消息发送给多个消费者 交换机模式:topic 相比于direct匹配模式,匹配routingKey时,topic模式下不仅支持完全匹配,还支持两种特殊的匹配方式 #:可以匹配一个或多个字符 *:可...

人觉非常君
46分钟前
0
0
[译]为什么(要使用)GNU Affero GPL?

#为什么(要使用)GNU Affero GPL? 作者信息:Copyright © 2010, 2013, 2014, 2015 Free Software Foundation, Inc. This page is licensed under a Creative Commons Attribution-NoDeriv......

ICE冰焰火灵X
47分钟前
0
0
apollox-lua 示例

这个项目是从openn2o里迁出的项目。 示例地址 apollox-lua.js 是把js翻译成lua的库。支持两种不同的模态, 在编译工程的时候使用 可以用作openresty的代码翻译, 即用js代替lua。在web模式可...

钟元OSS
56分钟前
0
0
Ubuntu系统笔记 Linux系统

Ubuntu 16.04.3 Ubuntu系统,不适用yum, yum软件源都是RPM软件包,不是deb格式软件包,所以你即便是在Ubuntu上面安装了yum,也是完全用不了的。 不推荐 apt好于yum apt install screen...

阿锋zxf
58分钟前
0
0
Java面试中,遇到这类面试题最吃亏!

从你接触 Java开发到现在,你对 Java最直观的印象是什么呢?是它宣传的 “Compile once, run anywhere”,还是目前看已经有些过于形式主义的语法呢?你对于 Java平台到底了解到什么程度?请你...

Java大蜗牛
今天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部