Loading [MathJax]/jax/output/CommonHTML/config.js
前往小程序，Get更优阅读体验！
立即前往
文档建议反馈控制台
首页
学习
活动
专区
圈层
工具
MCP广场
文章/答案/技术大牛
发布
首页
学习
活动
专区
圈层
工具
MCP广场
返回腾讯云官网
社区首页 >专栏 >用awk写递归

用awk写递归

作者头像
窗户
发布于 2018-02-07 06:32:51
发布于 2018-02-07 06:32:51
1.6K00
代码可运行
举报
文章被收录于专栏：窗户窗户
运行总次数：0
代码可运行
关联问题
换一批

看到自己很多年前写的一篇帖子，觉得有些意义，转录过来，稍加修改。

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

代码语言：javascript
代码运行次数：0
运行
AI代码解释
复制
#!/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);
}
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就是所谓的“栈顶指针” 第三个是用字符串来模拟变量栈，字符串末尾就是“栈顶指针”，每个“局部变量”之间是用分号隔开 用随机数据测试一下这个应用：

代码语言：javascript
代码运行次数：0
运行
AI代码解释
复制
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'
2
9981
9981
right

3
9391
9391
right

1
9919
5257
wrong

2
9860
9860
right

3
9967
9967
right

3
9940
9940
right

3
9828
9828
right

2
9752
9752
right

3
9996
9996
right

2
9930
9930
right

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

代码语言：javascript
代码运行次数：0
运行
AI代码解释
复制
#!/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);
}

测试一下，

代码语言：javascript
代码运行次数：0
运行
AI代码解释
复制
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'
5
9904
9904
right

4
9823
9823
right

5
9975
9975
right

4
9966
9966
right

5
9683
9683
right

5
9981
9981
right

4
9983
9983
right

5
9966
9966
right

5
9967
9967
right

5
9870
9870
right

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

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

代码语言：javascript
代码运行次数：0
运行
AI代码解释
复制
#!/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);
}
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);
}
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2017-06-27 ，如有侵权请联系 cloudcommunity@tencent.com 删除
编程算法

本文分享自 作者个人站点/博客 前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ，欢迎热爱写作的你一起参与！

编程算法
评论
登录后参与评论
暂无评论
登录 后参与评论
推荐阅读
编辑精选文章
换一批
万字详解高可用架构设计
1605
Go 开发者必备：Protocol Buffers 入门指南
777
10分钟带你彻底搞懂分布式链路跟踪
437
多租户的 4 种常用方案
975
亿级月活的社交 APP，陌陌如何做到 3 分钟定位故障？
719
60页PPT全解：DeepSeek系列论文技术要点整理
1478
GO语言基础之条件语句switch
go
switch 是一个条件语句，用于将表达式的值与可能匹配的选项列表进行比较，并根据匹配情况执行相应的代码块。它可以被认为是替代多个if else子句的常用方式。
墨紫羽墨
2022/01/03
4220
awk工作常用技巧
面向对象编程
版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.net/haluoluo211/article/details/77766092
bear_fish
2018/09/14
8760
awk工作常用技巧
带你深层了解c语言指针
编程算法
arr1数组,arr2数组,arr3数组在内存中都有自己独立的内存空间, 我们将这三个一维数组的首元素地址放在一个新的指针的数组(arr)中,通过指针数组来访问这三个一维数组,效果就如同二维数组一样,但并不是真正的二维数组. 图解:
初阶牛
2023/02/27
2930
带你深层了解c语言指针
awk数组详解、实战
linuxunixhttps网络安全html
1.其它编程语言数组的下标一般从0开始,awk中数组下标默认从1开始,也可以从0开始设置:
全栈程序员站长
2022/09/06
5130
Python基础——判断和循环
break集合
判断 缩进代替大括号。 冒号（:）后换号缩进。 if test=100 if test>50: print('OK') print('test') if-elif-else test=5
py3study
2020/01/16
4710
【C++】vector（下）--下篇
c++stdvector测试字符串
关于第一部分，这段代码都是内置类型，它们也与类模板的初始化方式相同，这是因为T可以是任意的类型，当然也可以是int、double等内置类型，所以这里的构造遵从类模板
s-little-monster
2024/09/09
1020
【C++】vector（下）--下篇
JavaScript（五）：函数（闭包，eval）
javascript
1.函数的申明：三种方法： function命令 函数表达式：变量赋值 Function构造函数 1 //method 1: function命令 2 function test(){ 3 console.log('hello function'); 4 } 5 6 //method 2:函数表达式,赋值给变量 7 var test1=function(){//这是个匿名函数 8 console.log('hello function1'); 9 };//注意这里有分号
用户1149564
2018/01/11
1.5K0
JavaScript（五）：函数（闭包，eval）
技术分享 | 一文了解高并发限流算法
编程算法https网络安全python压力测试
作为热点频出的电商系统，经常遇到高并发，热点秒杀的场景。我们在开发设计高并发海量业务请求的系统时，通常利用三板斧：缓存、降级和限流来保障系统稳定性。
爱可生开源社区
2020/09/23
5430
技术分享 | 一文了解高并发限流算法
C++初阶：适合新手的手撕string类（模拟实现string类）
c++charsizestring函数
是Nero哦
2024/02/05
2560
C++初阶：适合新手的手撕string类（模拟实现string类）
Linux系统开发: 学习linux三剑客(awk、sed、grep)(下)
linuxunix编程算法正则表达式express
这篇文章是 <Linux开发: 学习linux三剑客(awk、sed、grep)(上)>的续集。
DS小龙哥
2022/01/27
4.9K0
Linux系统开发: 学习linux三剑客(awk、sed、grep)(下)
从零构建以太坊（Ethereum）智能合约到项目实战——学习笔记6
编程算法
 int/uint：变长的有符号或无符号整型。变量支持的步长以8递增，支持从uint8到uint256，以及int8到int256。需要注意的是，uint和int默认代表的是uint256和int256.
墨文
2020/02/28
8870
从零构建以太坊（Ethereum）智能合约到项目实战——学习笔记6
Redis 字符串(Strings) 复习
云数据库 Redis®存储编程算法数据结构
字符串是Redis最简单的储存类型，它存储的值可以是字符串、整数或者浮点数，对整个字符串或者字符串的其中一部分执行操作;对整数或者浮点数执行自增（increment)或者自减(decrement)操作。
陈大剩博客
2023/03/06
3980
Redis 字符串(Strings) 复习
Java关键字final、static使用总结
java
一、final 根据程序上下文环境，Java关键字final有“这是无法改变的”或者“终态的”含义，它可以修饰非抽象类、非抽象类成员方法和变量。你可能出于两种理解而需要阻止改变：设计或效率。 final类不能被继承，没有子类，final类中的方法默认是final的。 final方法不能被子类的方法覆盖，但可以被继承。 final成员变量表示常量，只能被赋值一次，赋值后值不再改变。 final不能用于修饰构造方法。
用户1112962
2018/07/03
8340
从零开始学web安全（3）
安全
根据文章内容为读者提供摘要总结。
IMWeb前端团队
2017/12/29
8870
从零开始学web安全（3）
Linux之awk命令详解(一)
linuxunixnode.js编程算法
awk是一个报告生成器，拥有强大的文本格式化能力。它的命名方式也是由三位大佬，分别叫Aho，Weinberger，Kernighan，的三个人，awk命令取得他们的名字首字母。
AsiaYe
2019/11/06
11.4K0
final关键字
编程算法
final可以修饰非抽象类、非抽象类成员方法和变量。 （1）final类：不能被继承，没有子类，final类中的方法默认是final的； （2）final方法：不能被子类的方法覆盖，但可以被继承； （3）final成员变量：表示常量，只能被赋值一次，赋值后值不再改变； （4）final不能用于修饰构造方法。 （父类的private成员方法是不能被子类方法覆盖的，因此private类型的方法默认是final的） 1.final类 final类不能被继承，因此final类的成员方法没有机会被覆盖，默认是fi
Mister24
2018/05/14
8640
21天Python进阶学习挑战赛打卡------第4天(字典)
python编程算法存储
#例2：test中的键和值不变，我们从字典中获取相关的键和值，把这个值储存在new_points中 #再如下操作中，需要将new_points的整数类型转化为字符串
指剑
2022/08/26
8300
[Frombody]、[FromForm]傻傻分不清？ASP.NET Core获取请求参数方式总结
aspcore对象框架数据
一次HTTP请求，就是一次标准IO操作。请求是I，是输入；响应式O，是输出。任何web开发框架，其实都是在干这两件事：
郑子铭
2023/11/02
1.5K0
[Frombody]、[FromForm]傻傻分不清？ASP.NET Core获取请求参数方式总结
Python 学习入门（17）—— args, kwargs
python
The special syntax, *args and **kwargs in function definitions is used to pass a variable number of arguments to a function. The single asterisk form (*args) is used to pass a non-keyworded, variable-length argument list, and the double asterisk form is used to pass a keyworded, variable-length argument list. Here is an example of how to use the non-keyworded form. This example passes one formal (positional) argument, and two more variable length arguments.
阳光岛主
2019/02/19
3910
Linux awk 命令
node.js正则表达式linuxunix
AWK是一种处理文本文件的语言，是一个强大的文本分析工具。之所以叫AWK是因为其取了三位创始人Alfred Aho，Peter Weinberger, 和 Brian Kernighan 的 Family Name 的首字符。
狼啸风云
2019/11/03
4.3K0
推荐阅读
编辑精选文章
万字详解高可用架构设计Go 开发者必备：Protocol Buffers 入门指南10分钟带你彻底搞懂分布式链路跟踪
相关讨论
区块链是用什么技术写？地域写的是广州、上海。贵州用户怎样用？用php写的网站如何在浏览器中访问？
相关课程
轻量应用构建训练营云开发微搭低代码平台-一人构建企业级应用实战训练营AI代码助手快速上手训练营
GO语言基础之条件语句switch
4220
awk工作常用技巧
8760
带你深层了解c语言指针
2930
awk数组详解、实战
5130
Python基础——判断和循环
4710
【C++】vector（下）--下篇
1020
JavaScript（五）：函数（闭包，eval）
1.5K0
技术分享 | 一文了解高并发限流算法
5430
C++初阶：适合新手的手撕string类（模拟实现string类）
2560
Linux系统开发: 学习linux三剑客(awk、sed、grep)(下)
4.9K0
从零构建以太坊（Ethereum）智能合约到项目实战——学习笔记6
8870
Redis 字符串(Strings) 复习
3980
Java关键字final、static使用总结
8340
从零开始学web安全（3）
8870
Linux之awk命令详解(一)
11.4K0
final关键字
8640
21天Python进阶学习挑战赛打卡------第4天(字典)
8300
[Frombody]、[FromForm]傻傻分不清？ASP.NET Core获取请求参数方式总结
1.5K0
Python 学习入门（17）—— args, kwargs
3910
Linux awk 命令
4.3K0
相关推荐
GO语言基础之条件语句switch
更多 >
窗户0
LV.0
这个人很懒，什么都没有留下～
文章
71
获赞
370
专栏
1
作者相关精选
换一批
加入讨论
的问答专区 >
喵喵侠
1KOL擅长5个领域
相关课程
一站式学习中心 >
轻量应用构建训练营
2894人在学
云服务器
轻量应用服务器
云计算
云开发微搭低代码平台-一人构建企业级应用实战训练营
1881人在学
腾讯云微搭低代码
云开发
前端
1252人在学
前端
领券
💥开发者 MCP广场重磅上线！
精选全网热门MCP server，让你的AI更好用 🚀

腾讯云开发者

扫码关注腾讯云开发者

扫码关注腾讯云开发者

领取腾讯云代金券

热门产品

热门推荐

更多推荐

Copyright © 2013 - 2025 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有 

深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 深公网安备号 44030502008569

腾讯云计算（北京）有限责任公司 京ICP证150476号 |  京ICP备11018762号 | 京公网安备号11010802020287

问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档

Copyright © 2013 - 2025 Tencent Cloud.

All Rights Reserved. 腾讯云 版权所有

登录 后参与评论
7