go语言编程实现递归函数示例详解

目录
  • 前言
  • 函数中的 return
  • 递归的问题
  • 总结

前言

本篇文章主要是记录一下在 GScript 中实现递归调用时所遇到的坑,类似的问题在中文互联网上我几乎没有找到相关的内容,所以还是很有必要记录一下。

在开始之前还是简单介绍下本次更新的 GScript v0.0.9 所包含的内容:

  • 支持可变参数
  • 优化 append 函数语义
  • 优化编译错误信息
  • 最后一个就是支持递归调用

先看第一个可变参数:

//formats according to a format specifier and writes to standard output.
printf(string format, any ...a){}
//formats according to a format specifier and returns the resulting string.
string sprintf(string format, any ...a){}

以上是随着本次更新新增的两个标准函数,均支持可变参数,其中使用 ... 表示可变参数,调用时如下:

printf("hello %s ","123");
printf("hello-%s-%s ","123","abc");
printf("hello-%s-%d ","123",123);
string format = "this is %s ";
printf(format, "gscript");
string s = sprintf("nice to meet %s", "you");
assertEqual(s,"nice to meet you");

与大部分语言类似,可变参数本质上就是一个数组,所以可以拿来循环遍历:

int add(string s, int ...num){
	println(s);
	int sum = 0;
	for(int i=0;i<len(num);i++){
		int v = num[i];
		sum = sum+v;
	}
	return sum;
}
int x = add("abc", 1,2,3,4);
println(x);
assertEqual(x, 10);
// appends "v" to the end of a array "a"
append(any[] a, any v){}

之后是优化了内置函数 append() 的语义,本次优化来自于 issue12 的建议: github.com/crossoverJi…

// Before
int[] a={1,2,3};
println(a);
println();
a = append(a,4);
println(a);
// Output: [1 2 3 4]
// Now
int[] a={1,2,3};
println(a);
println();
append(a,4);
int b = a[3];
assertEqual(4, b);
println(a);
// Output: [1 2 3 4]

现在 append 之后不需要再重新赋值,也会追加数据,优化后这里看起来是一个值/引用传递的问题,但其实底层也是值传递,只是在语法上增加了这样的语法糖,帮使用者重新做了一次赋值。

之后是新增了编译错误信息提示,比如下面这段代码:

a+2;
b+c;

使用没有声明的变量,现在会直接编译失败:

1:0: undefined: a
2:0: undefined: b
2:2: undefined: c
class T{}
class T{}
// output:
2:0: class T redeclared in this block

重复声明之类的语法错误也有相关提示。

最后一个才是本次讨论的重点,也就是递归函数的支持。

int num(int x,int y){
	if (y==1 || y ==x) {
		return 1;
	}
	int v1 = num(x - 1, y - 1);
	return c;
}

再上一个版本中 int v1 = num(x - 1, y - 1); 这行代码是不会执行的,具体原因后文会分析。

现在利用递归便可以实现类似于打印杨辉三角之类的程序了:

int num(int x,int y){
	if (y==1 || y ==x) {
		return 1;
	}
    int v1 = num(x - 1, y - 1);
    int v2 = num(x - 1, y);
	int c = v1+v2;
    // int c = num(x - 1, y - 1)+num(x - 1, y);
	return c;
}
printTriangle(int row){
	for (int i = 1; i <= row; i++) {
        for (int j = 1; j <= row - i; j++) {
           print(" ");
        }
        for (int j = 1; j <= i; j++) {
            print(num(i, j) + " ");
        }
        println("");
    }
}
printTriangle(7);
// output:
      1
     1 1
    1 2 1
   1 3 3 1
  1 4 6 4 1
 1 5 10 10 5 1
1 6 15 20 15 6 1

函数中的 return

int num(int x,int y){
	if (y==1 || y ==x) {
		return 1;
	}
	int v1 = num(x - 1, y - 1);
	return c;
}

现在我们来看看这样的代码为什么执行完 return 1 之后就不会执行后边的语句了。

其实在此之前我首先解决的时候函数 return 后不能执行后续 statement 的需求,其实正好就是上文提到的逻辑,只是这里是递归而已。

先把代码简化一下方便分析:

int f1(int a){
	if (a==10){
		return 10;
	}
	println("abc");
}

当参数 a 等于 10 的时候确实不能执行后续的打印语句了,那么如何实现该需求呢?

以正常人类的思考方式:当我们执行完 return 语句的时候,就应该标记该语句所属的函数直接返回,不能在执行后续的 statement

可是这应该如何实操呢?

其实看看 AST 就能明白了:

当碰到 return 语句的时,会递归向上遍历语法树,标记上所有 block 节点表明这个 block 后续的语句不再执行了,同时还得把返回值记录下来。

这样当执行到下一个 statement 时,也就是 println("abc"); 则会判断他所属的 block 是否有被标记,如果有则直接返回,这样便实现了 return 语句不执行后续代码。

部分实现代码如下:

// 在 return 的时候递归向上扫描所有的 Block,并打上标记,用于后面执行 return 的时候直接返回。
func (v *Visitor) scanBlockStatementCtx(tree antlr.ParseTree, value interface{}) {
	context, ok := tree.(*parser.BlockContext)
	if ok {
		if v.blockCtx2Mark == nil {
			v.blockCtx2Mark = make(map[*parser.BlockContext]interface{})
		}
		v.blockCtx2Mark[context] = value
	}
	if tree.GetParent() != nil {
		v.scanBlockStatementCtx(tree.GetParent().(antlr.ParseTree), value)
	}
}

源码地址: github.com/crossoverJi…

递归的问题

但同时问题也来了,就是递归的时候也不会执行后续的递归代码了。

其实解决问题的方法也很简单,就是在判断是否需要直接返回那里新增一个条件,这个 block 中不存在递归调用。

所以我们就得先知道这个 block 中是否存在递归调用。

整个过程有以下几步:

  • 编译期:在函数声明处记录下函数与当前 context 的映射关系。
  • 编译期:扫描 statement 时,取出该 statementcontext 所对应的函数。
  • 编译期:扫描到的 statement 如果是一个函数调用,则判断该函数是否为该 block 中的函数,也就是第二步取出的函数。
  • 编译期:如果两个函数相等,则将当前 block 标记为递归调用。
  • 运行期:在刚才判断 return 语句处,额外多出判断当前 block 是否为递归调用,如果是则不能返回。

部分代码如下:

github.com/crossoverJi…

总结

这里的递归调用其实卡了我挺长时间的,思路是有的,但是写出来的代码总是和预期不符,当天晚上坐在电脑面前到凌晨两三点,百思不得其解。

最后受不了上床休息的时候,突然一个灵光乍现让我想到了解决方案,于是第二天起了个早床赶忙实践,还真给解决了。

所以有些时候碰到棘手问题时给自己放松一下,往往会有出其不意的效果。

最后是目前的递归在某些情况下性能还有些问题,后续会尽量将这些标记过程都放在编译期,编译慢点没事,但运行时慢那就有问题了。

之后还会继续优化运行时的异常,目前是直接 panic,堆栈也没有,体感非常不好;欢迎感兴趣的朋友试用反馈bug。

源码地址:

github.com/crossoverJi…

以上就是go语言编程实现递归函数示例详解的详细内容,更多关于go 递归函数的资料请关注我们其它相关文章!

(0)

相关推荐

  • Go递归修改文件名的实例代码

    在生活中我们往往有这样的需求,就是从网上找的文件资源经常包含了一些无用信息,而且在它的子目录下也同样存在,如果我们手动一个个的修改的话会特别麻烦,也特别耗时,我们可以考虑把这件事交给计算机来做. 如下图,我的桌面有一个名为dir[我爱你]的目录,而且这个目录下的子目录和文件都包含[我爱你],这个[我爱你]对于我们来说是完全无用的,我们可以用Go的文件操作库来递归对文件进行重命名,把不需要的名字替换为空 示例代码: package main import ( "bufio" "

  • golang通过递归遍历生成树状结构的操作

    业务场景: 一个机构查询科室信息的时候,希望返回树状结构的嵌套格式; 解决办法: 通过递归和指针,嵌套成对应的结构体; 借鉴了前人的代码,但是最后递归的指针调用自己也是调试了半天才出来,这里献上完整的示例代码. package main import ( "fmt" "encoding/json" ) type dept struct { DeptId string `json:"deptId"` FrameDeptStr string `jso

  • Golang 删除文件并递归删除空目录的操作

    目的: 删除文件之后,如果目录为空,递归删除为空的目录. svr.dataDir指目录的最外层,递归删除目录的时候判断到这一层即可. eg:/Users/danny/data func deleteFileOnDisk(localPath string) { log.Debugf("remove file: %s", localPath) if err := os.Remove(localPath); err != nil { log.Error(err) } dirsList :=

  • 深入解析Go语言编程中的递归使用

    递归是以相似的方式重复项目的过程.同样适用于编程语言中,如果一个程序可以让你调用同一个函数被调用的函数,递归调用函数内使用如下. 复制代码 代码如下: func recursion() {    recursion() /* function calls itself */ } func main() {    recursion() } Go编程语言支持递归,即要调用的函数本身.但是在使用递归时,程序员需要谨慎确定函数的退出条件,否则会造成无限循环. 递归函数是解决许多数学问题想计算一个数阶乘

  • 使用go和python递归删除.ds store文件的方法

    python版本: 复制代码 代码如下: #!/usr/bin/env pythonimport os, sys; def walk(path): print "cd directory:"+path for item in os.listdir(path): try: if(item == ".DS_Store"): global count count = count+1 print " find file .Ds_Store" os.rem

  • go语言编程实现递归函数示例详解

    目录 前言 函数中的 return 递归的问题 总结 前言 本篇文章主要是记录一下在 GScript 中实现递归调用时所遇到的坑,类似的问题在中文互联网上我几乎没有找到相关的内容,所以还是很有必要记录一下. 在开始之前还是简单介绍下本次更新的 GScript v0.0.9 所包含的内容: 支持可变参数 优化 append 函数语义 优化编译错误信息 最后一个就是支持递归调用 先看第一个可变参数: //formats according to a format specifier and writ

  • Kotlin语言编程Regex正则表达式实例详解

    目录 前言 Regex 构造函数 常用正则表达方法 示例展示 1.containsMatchIn(input: CharSequence) 包含指定字符串 2.matches(input: CharSequence) 匹配字符串 3.find(input: CharSequence, startIndex: Int = 0) 查找字符串,并返回第一次出现 4.findAll(input: CharSequence, startIndex: Int = 0) 查找字符串,返回所有出现的次数 5.r

  • Python面向对象编程repr方法示例详解

    目录 为什么要讲 __repr__ 重写 __repr__ 方法 str() 和 repr() 的区别 为什么要讲 __repr__ 在 Python 中,直接 print 一个实例对象,默认是输出这个对象由哪个类创建的对象,以及在内存中的地址(十六进制表示) 假设在开发调试过程中,希望使用 print 实例对象时,输出自定义内容,就可以用 __repr__ 方法了 或者通过 repr() 调用对象也会返回 __repr__ 方法返回的值 是不是似曾相识....没错..和 __str__ 一样的

  • Go语言基础模板设计模式示例详解

    目录 概述 模板模式生活案例 策略模式涉及到两个角色 UML 总结 示例 概述 模板方法模式定义了一个算法的步骤,并允许子类别为一个或多个步骤提供其实践方式.让子类别在不改变算法架构的情况下,重新定义算法中的某些步骤 确定了步骤的执行顺序,单某些步骤因环境或人等因素具体实现是未知的 模板模式生活案例 请客吃饭[点菜->吃东西->结账],每个人点菜不一样,吃东西不一样,结账也不一样从某地到某地[起点->出行方式->终点]起点和终点不一一样,但是每个人出行方式是不一样的 Go没有封装.

  • C语言进阶栈帧示例详解教程

    目录 正片开始 栈有什么用? 寄存器 main函数创建 局部变量创建 函数部分 形参与实参 正片开始 今天来讲讲我对栈帧创建与销毁的拙见.理解什么是栈帧首先知道什么是栈: 在数据结构中, 栈是限定仅在表尾进行插入或删除操作的线性表.栈是一种数据结构,它按照后进先出的原则存储数据,先进入的数据被压入栈底,最后的数据在栈顶,需要读数据的时候从栈顶开始弹出数据. 栈有什么用? 在计算机系统中,栈也可以称之为栈内存是一个具有动态内存区域,存储函数内部(包括main函数)的局部变量和方法调用和函数参数值,

  • C语言实现队列的示例详解

    目录 前言 一. 什么是队列 二. 使用什么来实现栈 三. 队列的实现 3.1头文件 3.2 函数的实现 四.完整代码 前言 前一段时间,我们试着用C语言实现了数据结构中的顺序表,单链表,双向循环链表,栈.今天我们再用C语言来实现另一种特殊的线性结构:队列 一. 什么是队列 队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(head)进行删除操作,而在表的后端(tail)进行插入操作,和栈一样,队列是一种操作受限制的线性表.进行插入操作的端称为队尾,进行删除操作的端称为队头. 这个队列就可

  • C语言实现栈的示例详解

    目录 前言 一. 什么是栈 二. 使用什么来实现栈 三. 栈的实现 3.1 头文件 3.2 函数实现 3.3 完整代码 四. 栈的用处 前言 前一段时间,我们试着用C语言实现了数据结构中的顺序表,单链表,双向循环链表.今天我们再用C语言来实现另一种特殊的线性结构:栈 一. 什么是栈 栈(stack)又名堆栈,它是一种运算受限的线性表.限定仅在表尾进行插入和删除操作的线性表.这一端被称为栈顶,相对地,把另一端称为栈底.向一个栈插入新元素又称作进栈.入栈或压栈,它是把新元素放到栈顶元素的上面,使之成

  • C语言实现阶乘的示例详解

    目录 前言 1.阶乘实现 1.1理论步骤 1.2实践结果 2.连续乘层相加实现 2.1理论步骤 2.2实践结果 前言 在现实中,我们做数学题总会遇到阶乘问题,这在计算机中也不例外. 那我们应该怎么实现呢? 我记得很多老师在电脑上书写阶乘都是用!这个符号表示. 比如5的阶乘,写为5!. 这在C语言中是行不通的,下面我讲解C语言中阶乘的实现. 1.阶乘实现 1.1理论步骤 我们可以利用while.do……while.以及for等循环实现,实现功能如下: 我们先设置好3个变量,i.n(想要的阶层数).

  • Kotlin编程条件控制示例详解

    目录 本文总览 1. When 表达式 2. If 表达式 总结 本文总览 本篇来看看 Kotlin的条件控制,这一节知识点 建议与Java中的条件结构类比,会很好理解并记住. 1. When 表达式 在 Kotlin 用 when 来定义多个分支的条件表达式.Kotlin中这个语法与 java 中的 switch 语句非常类似.代码块的执行就是将参数与所有的分⽀条件顺序⽐较,直到满⾜某个分⽀条件:(示例 ) when (x) { 1 -> print("x == 1") 2 -

  • Kotlin编程基础数据类型示例详解

    目录 本文总览 1.数值类型 2.布尔型 3.字符串 3.1 字符串字面值 3.2 字符串模板 4.数组 4.1 普通数组 4.2 原⽣类型数组 5.类型检测和类型转换 5.1 智能转换 5.2 is 与 !is 操作符 5.3 转换操作符: as 与 as? 总结 本文总览 上一篇学习了Kotlin基础语法知识,本篇开始会深入探讨一下Kotlin各个基础语法点.首先来熟悉Kotlin的数据类型和类型转换版块. 1.数值类型 在Kotlin中提供了数值类型: 整数类型:Byte,Short,In

随机推荐