第go語(yǔ)言編程實(shí)現(xiàn)遞歸函數(shù)示例詳解目錄前言函數(shù)中的return遞歸的問(wèn)題總結(jié)

前言

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

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

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

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

//formatsaccordingtoaformatspecifierandwritestostandardoutput.

printf(stringformat,any...a){}

//formatsaccordingtoaformatspecifierandreturnstheresultingstring.

stringsprintf(stringformat,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);

stringformat="thisis%s";

printf(format,"gscript");

strings=sprintf("nicetomeet%s","you");

assertEqual(s,"nicetomeetyou");

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

intadd(strings,int...num){

println(s);

intsum=0;

for(inti=0;ilen(num);i++){

intv=num[i];

sum=sum+v;

returnsum;

intx=add("abc",1,2,3,4);

println(x);

assertEqual(x,10);

//appends"v"totheendofaarray"a"

append(any[]a,anyv){}

之后是優(yōu)化了內(nèi)置函數(shù)append()的語(yǔ)義，本次優(yōu)化來(lái)自于issue12的建議：/crossoverJi

//Before

int[]a={1,2,3};

println(a);

println();

a=append(a,4);

println(a);

//Output:[1234]

//Now

int[]a={1,2,3};

println(a);

println();

append(a,4);

intb=a[3];

assertEqual(4,b);

println(a);

//Output:[1234]

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

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

a+2;

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

1:0:undefined:a

2:0:undefined:b

2:2:undefined:c

classT{}

classT{}

//output:

2:0:classTredeclaredinthisblock

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

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

intnum(intx,inty){

if(y==1||y==x){

return1;

intv1=num(x-1,y-1);

returnc;

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

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

intnum(intx,inty){

if(y==1||y==x){

return1;

intv1=num(x-1,y-1);

intv2=num(x-1,y);

intc=v1+v2;

//intc=num(x-1,y-1)+num(x-1,y);

returnc;

printTriangle(introw){

for(inti=1;i=row;i++){

for(intj=1;j=row-i;j++){

print("");

for(intj=1;jj++){

print(num(i,j)+"");

println("");

printTriangle(7);

//output:

11

121

1331

14641

15101051

1615201561

函數(shù)中的return

intnum(intx,inty){

if(y==1||y==x){

return1;

intv1=num(x-1,y-1);

returnc;

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

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

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

intf1(inta){

if(a==10){

return10;

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ǔ)法樹，標(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(treeantlr.ParseTree,valueinterface{}){

context,ok:=tree.(*parser.BlockContext)

ifok{

ifv.blockCtx2Mark==nil{

v.blockCtx2Mark=make(map[*parser.BlockContext]interface{})

v.blockCtx2Mark[context]=value

iftree.GetParent()!=nil{

v.scanBlockStatementCtx(tree.GetParent().(antlr.ParseTree),value)

源碼地址：/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)用，如果是則不能返回。

部分代碼如下：

/crossoverJi

總結(jié)

這里的遞歸調(diào)用其實(shí)卡了我挺長(zhǎng)時(shí)間的，思路是有的，但是寫出來(lái)的代碼總是和預(yù)期不符，當(dāng)天晚上坐在電腦面前到凌晨?jī)扇c(diǎn)，百思不得其解。

最后受不了上床休息的時(shí)候，突然一個(gè)靈光乍現(xiàn)讓我想到了解決方案，于是第二天起了個(gè)早床趕忙實(shí)踐，還真給解決了。

所以有些時(shí)候碰到棘手問(wèn)題時(shí)給自己放松一下，往往會(huì)有出其