快捷導(dǎo)航

go語(yǔ)言編程實(shí)現(xiàn)遞歸函數(shù)示例詳解

更新時(shí)間：2022年09月27日 16:57:53 作者：crossoverJie

這篇文章主要為大家介紹了go語(yǔ)言編程實(shí)現(xiàn)遞歸函數(shù)示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪

前言

本篇文章主要是記錄一下在 GScript 中實(shí)現(xiàn)遞歸調(diào)用時(shí)所遇到的坑，類似的問(wèn)題在中文互聯(lián)網(wǎng)上我?guī)缀鯖](méi)有找到相關(guān)的內(nèi)容，所以還是很有必要記錄一下。

在開(kāi)始之前還是簡(jiǎn)單介紹下本次更新的 GScript v0.0.9 所包含的內(nèi)容：

支持可變參數(shù)
優(yōu)化 append 函數(shù)語(yǔ)義
優(yōu)化編譯錯(cuò)誤信息
最后一個(gè)就是支持遞歸調(diào)用

先看第一個(gè)可變參數(shù)：

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

以上是隨著本次更新新增的兩個(gè)標(biāo)準(zhǔn)函數(shù)，均支持可變參數(shù)，其中使用 ... 表示可變參數(shù)，調(diào)用時(shí)如下：

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");

與大部分語(yǔ)言類似，可變參數(shù)本質(zhì)上就是一個(gè)數(shù)組，所以可以拿來(lái)循環(huán)遍歷：

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

之后是優(yōu)化了內(nèi)置函數(shù) append() 的語(yǔ)義，本次優(yōu)化來(lái)自于 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]

現(xiàn)在 append 之后不需要再重新賦值，也會(huì)追加數(shù)據(jù)，優(yōu)化后這里看起來(lái)是一個(gè)值/引用傳遞的問(wèn)題，但其實(shí)底層也是值傳遞，只是在語(yǔ)法上增加了這樣的語(yǔ)法糖，幫使用者重新做了一次賦值。

之后是新增了編譯錯(cuò)誤信息提示，比如下面這段代碼：

a+2;
b+c;

使用沒(méi)有聲明的變量，現(xiàn)在會(huì)直接編譯失敗：

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

重復(fù)聲明之類的語(yǔ)法錯(cuò)誤也有相關(guān)提示。

最后一個(gè)才是本次討論的重點(diǎn)，也就是遞歸函數(shù)的支持。

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

再上一個(gè)版本中 int v1 = num(x - 1, y - 1); 這行代碼是不會(huì)執(zhí)行的，具體原因后文會(huì)分析。

現(xiàn)在利用遞歸便可以實(shí)現(xiàn)類似于打印楊輝三角之類的程序了：

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

函數(shù)中的 return

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

現(xiàn)在我們來(lái)看看這樣的代碼為什么執(zhí)行完 return 1 之后就不會(huì)執(zhí)行后邊的語(yǔ)句了。

其實(shí)在此之前我首先解決的時(shí)候函數(shù) return 后不能執(zhí)行后續(xù) statement 的需求，其實(shí)正好就是上文提到的邏輯，只是這里是遞歸而已。

先把代碼簡(jiǎn)化一下方便分析：

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

當(dāng)參數(shù) a 等于 10 的時(shí)候確實(shí)不能執(zhí)行后續(xù)的打印語(yǔ)句了，那么如何實(shí)現(xiàn)該需求呢？

以正常人類的思考方式：當(dāng)我們執(zhí)行完 return 語(yǔ)句的時(shí)候，就應(yīng)該標(biāo)記該語(yǔ)句所屬的函數(shù)直接返回，不能在執(zhí)行后續(xù)的 statement。

可是這應(yīng)該如何實(shí)操呢？

其實(shí)看看 AST 就能明白了：

當(dāng)碰到 return 語(yǔ)句的時(shí)，會(huì)遞歸向上遍歷語(yǔ)法樹(shù)，標(biāo)記上所有 block 節(jié)點(diǎn)表明這個(gè) block 后續(xù)的語(yǔ)句不再執(zhí)行了，同時(shí)還得把返回值記錄下來(lái)。

這樣當(dāng)執(zhí)行到下一個(gè) statement 時(shí)，也就是 println("abc"); 則會(huì)判斷他所屬的 block 是否有被標(biāo)記，如果有則直接返回，這樣便實(shí)現(xiàn)了 return 語(yǔ)句不執(zhí)行后續(xù)代碼。

部分實(shí)現(xiàn)代碼如下：

// 在 return 的時(shí)候遞歸向上掃描所有的 Block，并打上標(biāo)記，用于后面執(zhí)行 return 的時(shí)候直接返回。
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…

遞歸的問(wèn)題

但同時(shí)問(wèn)題也來(lái)了，就是遞歸的時(shí)候也不會(huì)執(zhí)行后續(xù)的遞歸代碼了。

其實(shí)解決問(wèn)題的方法也很簡(jiǎn)單，就是在判斷是否需要直接返回那里新增一個(gè)條件，這個(gè) block 中不存在遞歸調(diào)用。

所以我們就得先知道這個(gè) block 中是否存在遞歸調(diào)用。

整個(gè)過(guò)程有以下幾步：

編譯期：在函數(shù)聲明處記錄下函數(shù)與當(dāng)前 context 的映射關(guān)系。
編譯期：掃描 statement 時(shí)，取出該 statement 的 context 所對(duì)應(yīng)的函數(shù)。
編譯期：掃描到的 statement 如果是一個(gè)函數(shù)調(diào)用，則判斷該函數(shù)是否為該 block 中的函數(shù)，也就是第二步取出的函數(shù)。
編譯期：如果兩個(gè)函數(shù)相等，則將當(dāng)前 block 標(biāo)記為遞歸調(diào)用。
運(yùn)行期：在剛才判斷 return 語(yǔ)句處，額外多出判斷當(dāng)前 block 是否為遞歸調(diào)用，如果是則不能返回。