首页 > 代码库 > 用awk写递归
用awk写递归
看到自己很多年前写的一篇帖子，觉得有些意义，转录过来，稍加修改。
awk是一种脚本语言，语法接近C语言，我比较喜欢用，gawk甚至可以支持tcp/ip,用起来非常方便。
awk也支持递归，只是awk不支持局部变量，所有的变量都是全局的，于是写递归有些麻烦。本文说白了，也只是借awk说一种编程的思路罢了。
原文如下：
awk支持函数，也支持递归。但awk并不支持局部变量，于是看上去递归函数很不好实现，因为在某一级调用函数的时候，里面的变量在该级调用还没有退出前就可能会被别的调用给修改掉，于是得到的结果会与期望并不一致。
我们考虑C语言，它的局部变量放在硬件支持的栈（一般用栈指针）内。于是我们就去思考，为什么是栈呢？我们来考虑一个具体的函数调用顺序：
f1调用f2;
f2调用f3;
f3返回；
f2调用f4;
f4调用f5;
f5返回；
f4返回；
f2返回；
f1返回；
按照这个循序，我们来思考每个函数开辟的栈空间：
f1的栈空间开辟(f1进栈）
f2的栈空间开辟(f2进栈）
f3的栈空间开辟(f3进栈）
f3的栈空间消亡(f3出栈）
f4的栈空间开辟(f4进栈）
f5的栈空间开辟(f5进栈）
f5的栈空间消亡(f5出栈）
f4的栈空间消亡(f4出栈）
f2的栈空间消亡(f2出栈）
f1的栈空间消亡(f1出栈）
原来跟我们数据结构里的栈的先进后出是一回事情，所以叫栈。
而当前的我们取的变量的地址都是相对于栈指针来说的，这是相对，而不是像全局变量的那种绝对。
于是我们可以受到启发，可以扩展这里的栈指针和地址的概念，awk的递归函数就可以出来了。
以下是用递归来算一个数组中的最大值（每递归一级就把数组分为两段，每段求最大值），只是举一个例子，可以扩展到任意应用。
#!/bin/awk -ffunc test1(a,start,len){ if(len<=1) return a[start]; x = test1(a,start,int(len/2)); y = test1(a,start+int(len/2),len-int(len/2)); return (x>y)?x:y;}func test2(a,start,len){ if(len<=1) return a[start]; testlen++; testa[testlen] = test2(a,start,int(len/2)); testlen++; testa[testlen] = test2(a,start+int(len/2),len-int(len/2)); testlen-=2; return (testa[testlen+1]>testa[testlen+2])?testa[testlen+1]:testa[testlen+2];}func test3(a,start,len){ if(len<=1) { return a[start]; } V = V";"test3(a,start,int(len/2)); V = V";"test3(a,start+int(len/2),len-int(len/2)); xx = V; sub(/.*;/,"",xx); sub(/;[^;]+$/,"",V); yy = V; sub(/.*;/,"",yy); sub(/;[^;]+$/,"",V); return int(xx)>int(yy)?int(xx):int(yy);}NR==1{ way=$1; print $1}NR==2{ max=$1; for(i=2;i<=NF;i++) if($i > max) max = $i; print max; for(i=1;i<=NF;i++) a[i] = $i; if(way == 2) print test2(a,1,NF); else if(way == 3) print test3(a,1,NF); else print test1(a,1,NF); exit(0);}这里面实现了三个递归函数，第一个是测试全局变量的污染，它是得不到正确的答案的
第二个是用数组来模拟变量栈，testlen就是所谓的“栈顶指针”
第三个是用字符串来模拟变量栈，字符串末尾就是“栈顶指针”，每个“局部变量”之间是用分号隔开
用随机数据测试一下这个应用：
linux-0gt0:/tmp/test # for((i=0;i<10;i++));do { echo $(($RANDOM % 3 + 1)); let count=$RANDOM%100+50; for((j=0;j<count;j++));do echo -n $(($RANDOM % 10000)) " "; done ; echo ; }|./1.awk ;done | sed -nr ‘N;N;p;/\n(.*)\n\1$/{s/.*/right\n/p;d;}; /^[23]/s/(.).*/\1 SO STRANGE!!!!!!!!!!!!!!!!!!!!!/p; s/.*/wrong\n/p‘299819981right393919391right199195257wrong298609860right399679967right399409940right398289828right297529752right399969996right299309930right当然，栈的数目自然也可以不只维系一个，test2和test3维系的是一个栈。
现在来实现test4和test5，两个函数是test2和test3的变体，各自维系两个栈。
#!/bin/awk -f#func test1(a,start,len)#{# if(len<=1)# return a[start];# x = test1(a,start,int(len/2));# y = test1(a,start+int(len/2),len-int(len/2));# return (x>y)?x:y;#}func test2(a,start,len){ if(len<=1) return a[start]; testlen++; testa[testlen] = test2(a,start,int(len/2)); testlen++; testa[testlen] = test2(a,start+int(len/2),len-int(len/2)); testlen-=2; return (testa[testlen+1]>testa[testlen+2])?testa[testlen+1]:testa[testlen+2];}func test3(a,start,len){ if(len<=1) { return a[start]; } V = V";"test3(a,start,int(len/2)); V = V";"test3(a,start+int(len/2),len-int(len/2)); xx = V; sub(/.*;/,"",xx); sub(/;[^;]+$/,"",V); yy = V; sub(/.*;/,"",yy); sub(/;[^;]+$/,"",V); return int(xx)>int(yy)?int(xx):int(yy);}func test4(a,start,len){ if(len<=1) return a[start]; testlenx++; testleny++; testax[testlenx] = test4(a,start,int(len/2)); testay[testleny] = test4(a,start+int(len/2),len-int(len/2)); testlenx-=1; testleny-=1; return (testax[testlenx+1]>testay[testleny+1])?testax[testlenx+1]:testay[testleny+1];}func test5(a,start,len){ if(len<=1) { return a[start]; } V1 = V1";"test5(a,start,int(len/2)); V2 = V2";"test5(a,start+int(len/2),len-int(len/2)); xx = V1; sub(/.*;/,"",xx); sub(/;[^;]+$/,"",V1); yy = V2; sub(/.*;/,"",yy); sub(/;[^;]+$/,"",V2); return int(xx)>int(yy)?int(xx):int(yy);}NR==1{ way=$1; print $1}NR==2{ max=$1; for(i=2;i<=NF;i++) if($i > max) max = $i; print max; for(i=1;i<=NF;i++) a[i] = $i; if(way == 2) print test2(a,1,NF); else if(way == 3) print test3(a,1,NF); else if(way == 4) print test4(a,1,NF); else if(way == 5) print test5(a,1,NF); exit(0);}测试一下，
linux-0gt0:/tmp/test # for((i=0;i<10;i++));do { echo $(($RANDOM % 2 + 4)); let count=$RANDOM%100+50; for((j=0;j<count;j++));do echo -n $(($RANDOM % 10000)) " "; done ; echo ; }|./1.awk ;done | sed -nr ‘N;N;p;/\n(.*)\n\1$/{s/.*/right\n/p;d;}; /^[234]/s/(.).*/\1 SO STRANGE!!!!!!!!!!!!!!!!!!!!!/p; s/.*/wrong\n/p‘599049904right498239823right599759975right499669966right596839683right599819981right499839983right599669966right599679967right598709870right当然，test4和test5各自维系的两个栈其实差别和一个栈不大，因为两个栈是同时进栈同时出栈的。
其实，即使两个栈并非同时进出栈也是可以的，只是对于这里的例子来说写不出这么复杂。
实际上，任意多的栈，任意进出栈，都是可以的。
这样就可以做到更加灵活的应用。
软件的扩展性比硬件强，我想，这就是软件的用处吧。
还是这个取最大值,举个含有多个栈,每个栈入出并不完全一致的例子,这里的test6函数
#!/bin/awk -ffunc test1(a,start,len){ if(len<=1) return a[start]; x = test1(a,start,int(len/2)); y = test1(a,start+int(len/2),len-int(len/2)); return (x>y)?x:y;}func test2(a,start,len){ if(len<=1) return a[start]; testlen++; testa[testlen] = test2(a,start,int(len/2)); testlen++; testa[testlen] = test2(a,start+int(len/2),len-int(len/2)); testlen-=2; return (testa[testlen+1]>testa[testlen+2])?testa[testlen+1]:testa[testlen+2];}func test3(a,start,len){ if(len<=1) { return a[start]; } V = V";"test3(a,start,int(len/2)); V = V";"test3(a,start+int(len/2),len-int(len/2)); xx = V; sub(/.*;/,"",xx); sub(/;[^;]+$/,"",V); yy = V; sub(/.*;/,"",yy); sub(/;[^;]+$/,"",V); return int(xx)>int(yy)?int(xx):int(yy);}func test4(a,start,len){ if(len<=1) return a[start]; testlenx++; testleny++; testax[testlenx] = test4(a,start,int(len/2)); testay[testleny] = test4(a,start+int(len/2),len-int(len/2)); testlenx-=1; testleny-=1; return (testax[testlenx+1]>testay[testleny+1])?testax[testlenx+1]:testay[testleny+1];}func test5(a,start,len){ if(len<=1) { return a[start]; } V1 = V1";"test5(a,start,int(len/2)); V2 = V2";"test5(a,start+int(len/2),len-int(len/2)); xx = V1; sub(/.*;/,"",xx); sub(/;[^;]+$/,"",V1); yy = V2; sub(/.*;/,"",yy); sub(/;[^;]+$/,"",V2); return int(xx)>int(yy)?int(xx):int(yy);}func test6(a,start,len){ if(len <= 1) { return a[start]; } else if(len == 2) { return (a[start]>a[start+1])?a[start]:a[start+1]; } else if(len == 3) { var1 = (a[start]>a[start+1])?a[start]:a[start+1]; return (var1>a[start+2])?var1:a[start+2]; } var2 = int(rand()*10000)%3+2; if(var2 == 2) { testlenx++; testleny++; testax[testlenx] = test6(a,start,int(len/2)); testay[testleny] = test6(a,start+int(len/2),len-int(len/2)); testlenx-=1; testleny-=1; return (testax[testlenx+1]>testay[testleny+1])?testax[testlenx+1]:testay[testleny+1]; } else if(var2 == 3) { testlenx++; testleny++; testlenz++; testax[testlenx] = test6(a,start,int(len/3)); testay[testleny] = test6(a,start+int(len/3),int(len/3)); testaz[testlenz] = test6(a,start+2*int(len/3),len-2*int(len/3)); testlenx-=1; testleny-=1; testlenz-=1; var1 = (testax[testlenx+1]>testay[testleny+1])?testax[testlenx+1]:testay[testleny+1]; return ((var1>testaz[testlenz+1])?var1:testaz[testlenz+1]); } else if(var2 == 4) { testlenx++; testleny++; testlenz++; testlenA++; testax[testlenx] = test6(a,start,int(len/4)); testay[testleny] = test6(a,start+int(len/4),int(len/4)); testaz[testlenz] = test6(a,start+2*int(len/4),int(len/4)); testaA[testlenA] = test6(a,start+3*int(len/4),len-3*int(len/4)); testlenx-=1; testleny-=1; testlenz-=1; testlenA-=1; var1 = (testax[testlenx+1]>testay[testleny+1])?testax[testlenx+1]:testay[testleny+1]; var4 = (testaz[testlenz+1]>testaA[testlenA+1])?testaz[testlenz+1]:testaA[testlenA+1]; return ((var1>var4)?var1:var4); }}BEGIN { srand(systime());}NR==1{ way=$1; print $1}NR==2{ max=$1; for(i=2;i<=NF;i++) if($i > max) max = $i; print max; for(i=1;i<=NF;i++) a[i] = $i; if(way == 2) print test2(a,1,NF); else if(way == 3) print test3(a,1,NF); else if(way == 4) print test4(a,1,NF); else if(way == 5) print test5(a,1,NF); else if(way == 6) print test6(a,1,NF); else print test1(a,1,NF); exit(0);}
用awk写递归
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。