用awk写递归函数

cjaizss

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的递归函数就可以出来了。
以下是用递归来算一个数组中的最大值（每递归一级就把数组分为两段，每段求最大值），只是举一个例子，可以扩展到任意应用。

1. 
   
2. #!/bin/awk -f
   
3. func test1(a,start,len)
   
4. {
   
5.         if(len<=1)
   
6.                 return a[start];
   
7.         x = test1(a,start,int(len/2));
   
8.         y = test1(a,start+int(len/2),len-int(len/2));
   
9.         return (x>y)?x:y;
   
10. }
    
11. func test2(a,start,len)
    
12. {
    
13.         if(len<=1)
    
14.                 return a[start];
    
15.         testlen++;
    
16.         testa[testlen] = test2(a,start,int(len/2));
    
17.         testlen++;
    
18.         testa[testlen] = test2(a,start+int(len/2),len-int(len/2));
    
19.         testlen-=2;
    
20.         return (testa[testlen+1]>testa[testlen+2])?testa[testlen+1]:testa[testlen+2];
    
21. }
    
22. func test3(a,start,len)
    
23. {
    
24.         if(len<=1) {
    
25.                 return a[start];
    
26.         }
    
27.         V = V";"test3(a,start,int(len/2));
    
28.         V = V";"test3(a,start+int(len/2),len-int(len/2));
    
29.         xx = V;
    
30.         sub(/.*;/,"",xx);
    
31.         sub(/;[^;]+$/,"",V);
    
32.         yy = V;
    
33.         sub(/.*;/,"",yy);
    
34.         sub(/;[^;]+$/,"",V);
    
35.         return int(xx)>int(yy)?int(xx):int(yy);
    
36. }
    
37. NR==1{
    
38.         way=$1;
    
39.         print $1
    
40. }
    
41. NR==2{
    
42.         max=$1;
    
43.         for(i=2;i<=NF;i++)
    
44.                 if($i > max)
    
45.                         max = $i;
    
46.         print max;
    
47.         for(i=1;i<=NF;i++)
    
48.                 a[i] = $i;
    
49.         if(way == 2)
    
50.                 print test2(a,1,NF);
    
51.         else if(way == 3)
    
52.                 print test3(a,1,NF);
    
53.         else
    
54.                 print test1(a,1,NF);
    
55.         exit(0);
    
56. }
    
57. 
    

复制代码

这里面实现了三个递归函数，第一个是测试全局变量的污染，它是得不到正确的答案的
第二个是用数组来模拟变量栈，testlen就是所谓的“栈顶指针”
第三个是用字符串来模拟变量栈，字符串末尾就是“栈顶指针”，每个“局部变量”之间是用分号隔开
用随机数据测试一下这个应用：

1. 
   
2. 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'
   
3. 2
   
4. 9981
   
5. 9981
   
6. right
   
7. 
   
8. 3
   
9. 9391
   
10. 9391
    
11. right
    
12. 
    
13. 1
    
14. 9919
    
15. 5257
    
16. wrong
    
17. 
    
18. 2
    
19. 9860
    
20. 9860
    
21. right
    
22. 
    
23. 3
    
24. 9967
    
25. 9967
    
26. right
    
27. 
    
28. 3
    
29. 9940
    
30. 9940
    
31. right
    
32. 
    
33. 3
    
34. 9828
    
35. 9828
    
36. right
    
37. 
    
38. 2
    
39. 9752
    
40. 9752
    
41. right
    
42. 
    
43. 3
    
44. 9996
    
45. 9996
    
46. right
    
47. 
    
48. 2
    
49. 9930
    
50. 9930
    
51. right
    
52. 
    

复制代码

补充：这是一种思路，与你使用在什么语言，什么场合，甚至数字电路的设计，没有关系

[ 本帖最后由 cjaizss 于 2009-8-23 23:48 编辑 ]

MYSQLER

哎～我啥时候能到你的高度啊

cjaizss

当然，栈的数目自然也可以不只维系一个，test2和test3维系的是一个栈。
现在来实现test4和test5，两个函数是test2和test3的变体，各自维系两个栈。

1. 
   
2. #!/bin/awk -f
   
3. #func test1(a,start,len)
   
4. #{
   
5. #       if(len<=1)
   
6. #               return a[start];
   
7. #       x = test1(a,start,int(len/2));
   
8. #       y = test1(a,start+int(len/2),len-int(len/2));
   
9. #       return (x>y)?x:y;
   
10. #}
    
11. func test2(a,start,len)
    
12. {
    
13.         if(len<=1)
    
14.                 return a[start];
    
15.         testlen++;
    
16.         testa[testlen] = test2(a,start,int(len/2));
    
17.         testlen++;
    
18.         testa[testlen] = test2(a,start+int(len/2),len-int(len/2));
    
19.         testlen-=2;
    
20.         return (testa[testlen+1]>testa[testlen+2])?testa[testlen+1]:testa[testlen+2];
    
21. }
    
22. func test3(a,start,len)
    
23. {
    
24.         if(len<=1) {
    
25.                 return a[start];
    
26.         }
    
27.         V = V";"test3(a,start,int(len/2));
    
28.         V = V";"test3(a,start+int(len/2),len-int(len/2));
    
29.         xx = V;
    
30.         sub(/.*;/,"",xx);
    
31.         sub(/;[^;]+$/,"",V);
    
32.         yy = V;
    
33.         sub(/.*;/,"",yy);
    
34.         sub(/;[^;]+$/,"",V);
    
35.         return int(xx)>int(yy)?int(xx):int(yy);
    
36. }
    
37. func test4(a,start,len)
    
38. {
    
39.         if(len<=1)
    
40.                 return a[start];
    
41.         testlenx++;
    
42.         testleny++;
    
43.         testax[testlenx] = test4(a,start,int(len/2));
    
44.         testay[testleny] = test4(a,start+int(len/2),len-int(len/2));
    
45.         testlenx-=1;
    
46.         testleny-=1;
    
47.         return (testax[testlenx+1]>testay[testleny+1])?testax[testlenx+1]:testay[testleny+1];
    
48. }
    
49. func test5(a,start,len)
    
50. {
    
51.         if(len<=1) {
    
52.                 return a[start];
    
53.         }
    
54.         V1 = V1";"test5(a,start,int(len/2));
    
55.         V2 = V2";"test5(a,start+int(len/2),len-int(len/2));
    
56.         xx = V1;
    
57.         sub(/.*;/,"",xx);
    
58.         sub(/;[^;]+$/,"",V1);
    
59.         yy = V2;
    
60.         sub(/.*;/,"",yy);
    
61.         sub(/;[^;]+$/,"",V2);
    
62.         return int(xx)>int(yy)?int(xx):int(yy);
    
63. }
    
64. NR==1{
    
65.         way=$1;
    
66.         print $1
    
67. }
    
68. NR==2{
    
69.         max=$1;
    
70.         for(i=2;i<=NF;i++)
    
71.                 if($i > max)
    
72.                         max = $i;
    
73.         print max;
    
74.         for(i=1;i<=NF;i++)
    
75.                 a[i] = $i;
    
76.         if(way == 2)
    
77.                 print test2(a,1,NF);
    
78.         else if(way == 3)
    
79.                 print test3(a,1,NF);
    
80.         else if(way == 4)
    
81.                 print test4(a,1,NF);
    
82.         else if(way == 5)
    
83.                 print test5(a,1,NF);
    
84.         exit(0);
    
85. }
    

复制代码

测试一下，

1. 
   
2. 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'
   
3. 5
   
4. 9904
   
5. 9904
   
6. right
   
7. 
   
8. 4
   
9. 9823
   
10. 9823
    
11. right
    
12. 
    
13. 5
    
14. 9975
    
15. 9975
    
16. right
    
17. 
    
18. 4
    
19. 9966
    
20. 9966
    
21. right
    
22. 
    
23. 5
    
24. 9683
    
25. 9683
    
26. right
    
27. 
    
28. 5
    
29. 9981
    
30. 9981
    
31. right
    
32. 
    
33. 4
    
34. 9983
    
35. 9983
    
36. right
    
37. 
    
38. 5
    
39. 9966
    
40. 9966
    
41. right
    
42. 
    
43. 5
    
44. 9967
    
45. 9967
    
46. right
    
47. 
    
48. 5
    
49. 9870
    
50. 9870
    
51. right
    
52. 
    

复制代码

当然，test4和test5各自维系的两个栈其实差别和一个栈不大，因为两个栈是同时进栈同时出栈的。
其实，即使两个栈并非同时进出栈也是可以的，只是对于这里的例子来说写不出这么复杂。
实际上，任意多的栈，任意进出栈，都是可以的。
这样就可以做到更加灵活的应用。
软件的扩展性比硬件强，我想，这就是软件的用处吧。

xinyv

好帖，拜读了。

cjaizss

还是这个取最大值,举个含有多个栈,每个栈入出并不完全一致的例子,这里的test6函数

1. 
   
2. #!/bin/awk -f
   
3. func test1(a,start,len)
   
4. {
   
5.         if(len<=1)
   
6.                 return a[start];
   
7.         x = test1(a,start,int(len/2));
   
8.         y = test1(a,start+int(len/2),len-int(len/2));
   
9.         return (x>y)?x:y;
   
10. }
    
11. func test2(a,start,len)
    
12. {
    
13.         if(len<=1)
    
14.                 return a[start];
    
15.         testlen++;
    
16.         testa[testlen] = test2(a,start,int(len/2));
    
17.         testlen++;
    
18.         testa[testlen] = test2(a,start+int(len/2),len-int(len/2));
    
19.         testlen-=2;
    
20.         return (testa[testlen+1]>testa[testlen+2])?testa[testlen+1]:testa[testlen+2];
    
21. }
    
22. func test3(a,start,len)
    
23. {
    
24.         if(len<=1) {
    
25.                 return a[start];
    
26.         }
    
27.         V = V";"test3(a,start,int(len/2));
    
28.         V = V";"test3(a,start+int(len/2),len-int(len/2));
    
29.         xx = V;
    
30.         sub(/.*;/,"",xx);
    
31.         sub(/;[^;]+$/,"",V);
    
32.         yy = V;
    
33.         sub(/.*;/,"",yy);
    
34.         sub(/;[^;]+$/,"",V);
    
35.         return int(xx)>int(yy)?int(xx):int(yy);
    
36. }
    
37. func test4(a,start,len)
    
38. {
    
39.         if(len<=1)
    
40.                 return a[start];
    
41.         testlenx++;
    
42.         testleny++;
    
43.         testax[testlenx] = test4(a,start,int(len/2));
    
44.         testay[testleny] = test4(a,start+int(len/2),len-int(len/2));
    
45.         testlenx-=1;
    
46.         testleny-=1;
    
47.         return (testax[testlenx+1]>testay[testleny+1])?testax[testlenx+1]:testay[testleny+1];
    
48. }
    
49. func test5(a,start,len)
    
50. {
    
51.         if(len<=1) {
    
52.                 return a[start];
    
53.         }
    
54.         V1 = V1";"test5(a,start,int(len/2));
    
55.         V2 = V2";"test5(a,start+int(len/2),len-int(len/2));
    
56.         xx = V1;
    
57.         sub(/.*;/,"",xx);
    
58.         sub(/;[^;]+$/,"",V1);
    
59.         yy = V2;
    
60.         sub(/.*;/,"",yy);
    
61.         sub(/;[^;]+$/,"",V2);
    
62.         return int(xx)>int(yy)?int(xx):int(yy);
    
63. }
    
64. func test6(a,start,len)
    
65. {
    
66.         if(len <= 1) {
    
67.                 return a[start];
    
68.         } else if(len == 2) {
    
69.                 return (a[start]>a[start+1])?a[start]:a[start+1];
    
70.         } else if(len == 3) {
    
71.                 var1 = (a[start]>a[start+1])?a[start]:a[start+1];
    
72.                 return (var1>a[start+2])?var1:a[start+2];
    
73.         }
    
74.         var2 = int(rand()*10000)%3+2;
    
75.         if(var2 == 2) {
    
76.                 testlenx++;
    
77.                 testleny++;
    
78.                 testax[testlenx] = test6(a,start,int(len/2));
    
79.                 testay[testleny] = test6(a,start+int(len/2),len-int(len/2));
    
80.                 testlenx-=1;
    
81.                 testleny-=1;
    
82.                 return (testax[testlenx+1]>testay[testleny+1])?testax[testlenx+1]:testay[testleny+1];
    
83.         } else if(var2 == 3) {
    
84.                 testlenx++;
    
85.                 testleny++;
    
86.                 testlenz++;
    
87.                 testax[testlenx] = test6(a,start,int(len/3));
    
88.                 testay[testleny] = test6(a,start+int(len/3),int(len/3));
    
89.                 testaz[testlenz] = test6(a,start+2*int(len/3),len-2*int(len/3));
    
90.                 testlenx-=1;
    
91.                 testleny-=1;
    
92.                 testlenz-=1;
    
93.                 var1 = (testax[testlenx+1]>testay[testleny+1])?testax[testlenx+1]:testay[testleny+1];
    
94.                 return ((var1>testaz[testlenz+1])?var1:testaz[testlenz+1]);
    
95.         } else if(var2 == 4) {
    
96.                 testlenx++;
    
97.                 testleny++;
    
98.                 testlenz++;
    
99.                 testlenA++;
    
100.                 testax[testlenx] = test6(a,start,int(len/4));
     
101.                 testay[testleny] = test6(a,start+int(len/4),int(len/4));
     
102.                 testaz[testlenz] = test6(a,start+2*int(len/4),int(len/4));
     
103.                 testaA[testlenA] = test6(a,start+3*int(len/4),len-3*int(len/4));
     
104.                 testlenx-=1;
     
105.                 testleny-=1;
     
106.                 testlenz-=1;
     
107.                 testlenA-=1;
     
108.                 var1 = (testax[testlenx+1]>testay[testleny+1])?testax[testlenx+1]:testay[testleny+1];
     
109.                 var4 = (testaz[testlenz+1]>testaA[testlenA+1])?testaz[testlenz+1]:testaA[testlenA+1];
     
110.                 return ((var1>var4)?var1:var4);
     
111.         }
     
112. }
     
113. BEGIN {
     
114.         srand(systime());
     
115. }
     
116. NR==1{
     
117.         way=$1;
     
118.         print $1
     
119. }
     
120. NR==2{
     
121.         max=$1;
     
122.         for(i=2;i<=NF;i++)
     
123.                 if($i > max)
     
124.                         max = $i;
     
125.         print max;
     
126.         for(i=1;i<=NF;i++)
     
127.                 a[i] = $i;
     
128.         if(way == 2)
     
129.                 print test2(a,1,NF);
     
130.         else if(way == 3)
     
131.                 print test3(a,1,NF);
     
132.         else if(way == 4)
     
133.                 print test4(a,1,NF);
     
134.         else if(way == 5)
     
135.                 print test5(a,1,NF);
     
136.         else if(way == 6)
     
137.                 print test6(a,1,NF);
     
138.         else
     
139.                 print test1(a,1,NF);
     
140.         exit(0);
     
141. }
     
142. 
     

复制代码

kwokcn

好帖，支持版主。：）
之前用过一次递归，仅供参考：
http://bbs.chinaunix.net/viewthr ... p;extra=&page=2

cjaizss

我觉得此类扩展思路的帖子，应该加个精了

xiaopan3322

自己什么时候才能够学好awk啊，哎哎哎……

cjaizss

自己什么时候才能够学好awk啊，哎哎哎……
xiaopan3322 发表于 2011-01-09 11:56

    够用就行，awk很强大，特别是gawk，多写写就熟悉了

cjaizss

够用就行，awk很强大，特别是gawk，多写写就熟悉了
cjaizss 发表于 2011-01-09 12:01

    但我这个文章不是特意为awk写的，只是提供一个思路而已