awk的递归

  版权申明:本文为博主窗户(Colin Cai)原创,欢迎转帖。如要转贴,必须注明原文网址

  http://www.cnblogs.com/Colin-Cai/p/9082551.html 

  作者:窗户

  QQ:6679072

  E-mail:6679072@qq.com

  想来惭愧,之前写的一篇文章《用awk写递归》里多少是传递了错误的信息。虽然那篇文章目的上是为了给出一种思路,但实际上awk是可以支持函数局部变量的。

  awk对于局部变量的支持比起大多数过程式语言来说很是怪异,它只在函数的参数里支持。所以如果想用局部变量,多少需要改变我们以前的一些习惯。

  于是我们使用这一点,就可以直接写出一个awk下面的递归。举个简单的例子,比如我们想输入一个数n,就算出1+2+...n的值。写法如下:

awk '
        function sum(n, other_sum)
        {
                return n==0?other_sum:sum(n-1, other_sum+n)
        }
        {
                print sum($1,0)
        }'

  sum在这里作为一个递归,接受两个参数,一个是n,一个是之前的累和结果。这种用法很像函数式编程,比如lisp系。

  以shceme为例

(define (sum n)
   (define (_sum n other_sum)
    (if (= n 0) other_sum (_sum (- n 1) (+ other_sum n))))
   (_sum n 0)
   )

  为了忏悔,我还是用awk写个函数式风格的汉诺塔程序吧。

#!/usr/bin/awk -f
function connect(a, b)
{
        return a "" b
}function other_pos(a, b)
{
        return 6-a-b;
}

function sub1(a)
{
        return a-1;
}

function eq(a, b)
{
        return a==b;
}

function hanoi2(n, from, to)
{
        return eq(n,0)? "": connect(connect(connect(hanoi2(sub1(n), from, other_pos(from,to)), " "),connect(from, "->")),connect(connect(to, " "),hanoi2(sub1(n), other_pos(from,to), to)))
}
function hanoi(n)
{
        return hanoi2(n, 1, 3)
}
{
        print hanoi($1)
}

  运行一下,尝试一下8块饼的汉诺塔怎么移动。

$ echo 8 | ./hanoi.awk 1->2 1->3 2->3 1->2 3->1 3->2 1->2 1->3 2->3 2->1 3->1 2->3 1->2 1->3 2->3 1->2 3->1 3->2 1->2 3->1 2->3 2->1 3->1 3->2 1->2 1->3 2->3 1->2 3->1 3->2 1->2 1->3 2->3 2->1 3->1 2->3 1->2 1->3 2->3 2->1 3->1 3->2 1->2 3->1 2->3 2->1 3->1 2->3 1->2 1->3 2->3 1->2 3->1 3->2 1->2 1->3 2->3 2->1 3->1 2->3 1->2 1->3 2->3 1->2 3->1 3->2 1->2 3->1 2->3 2->1 3->1 3->2 1->2 1->3 2->3 1->2 3->1 3->2 1->2 3->1 2->3 2->1 3->1 2->3 1->2 1->3 2->3 2->1 3->1 3->2 1->2 3->1 2->3 2->1 3->1 3->2 1->2 1->3 2->3 1->2 3->1 3->2 1->2 1->3 2->3 2->1 3->1 2->3 1->2 1->3 2->3 1->2 3->1 3->2 1->2 3->1 2->3 2->1 3->1 3->2 1->2 1->3 2->3 1->2 3->1 3->2 1->2 1->3 2->3 2->1 3->1 2->3 1->2 1->3 2->3 2->1 3->1 3->2 1->2 3->1 2->3 2->1 3->1 2->3 1->2 1->3 2->3 1->2 3->1 3->2 1->2 1->3 2->3 2->1 3->1 2->3 1->2 1->3 2->3 2->1 3->1 3->2 1->2 3->1 2->3 2->1 3->1 3->2 1->2 1->3 2->3 1->2 3->1 3->2 1->2 3->1 2->3 2->1 3->1 2->3 1->2 1->3 2->3 2->1 3->1 3->2 1->2 3->1 2->3 2->1 3->1 2->3 1->2 1->3 2->3 1->2 3->1 3->2 1->2 1->3 2->3 2->1 3->1 2->3 1->2 1->3 2->3 1->2 3->1 3->2 1->2 3->1 2->3 2->1 3->1 3->2 1->2 1->3 2->3 1->2 3->1 3->2 1->2 1->3 2->3 2->1 3->1 2->3 1->2 1->3 2->3 2->1 3->1 3->2 1->2 3->1 2->3 2->1 3->1 2->3 1->2 1->3 2->3 1->2 3->1 3->2 1->2 1->3 2->3 2->1 3->1 2->3 1->2 1->3 2->3

  注意,前面写函数式风格的时候,我最终还是使用了三目条件运算符,而没有搭建一个函数 

  function cond_op(cond, a, b)   {     return cond?a:b;   }

  因为如果这样搭建,必然会死循环,想想为什么?

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏我杨某人的青春满是悔恨

找零问题与动态规划

后来我发现在 leet code 也有类似的题,是个找零问题,就是不同面值的硬币组合成一个数有多少种情况。还挺有意思的,我就做了一下,用了递归:

1961
来自专栏机器人网

只会G代码不会宏,就别说你是数控师傅

一、变量 普通加工程序直接用数值指定G代码和移动距离;例如,GO1和X100.0。使用用户宏程序时,数值可以直接指定或用变量指定。当用变量时,变量值可用程序或用...

2874
来自专栏夏时

PHP 常用函数大全

5602
来自专栏用户2442861的专栏

限制QLineEdit的数值输入范围

QLineEdit *lineEdit = new QLineEdit(this);

1.2K1
来自专栏Laoqi's Linux运维专列

正则三剑客-awk

awk与前两个不同之处是支持分段处理; #mkdir awk; cp /etc/passwd awk/passwd         //前期准备,创建一个awk...

2825
来自专栏数据结构与算法

07:机器翻译

7:机器翻译 总时间限制: 1000ms 内存限制: 65536kB描述 小晨的电脑上安装了一个机器翻译软件,他经常用这个软件来翻译英语文章。 这个翻译软件...

4076
来自专栏Star先生的专栏

Tensorflow 术语表

本文主要简要介绍了广播操作、Graph(图)、Session(会话)、Tensor 等13个 Tensorflow 术语表。希望对大家了解学习 Tensorfl...

1.1K1
来自专栏蘑菇先生的技术笔记

探索C#之布隆过滤器(Bloom filter)

3025
来自专栏生信宝典

Python学习教程(二)

输入输出 交互式输入输出 在很多时候,你会想要让你的程序与用户(可能是你自己)交互。你会从用户那里得到输入,然后打印一些结果。我们可以分别使用raw_input...

2778
来自专栏SDNLAB

Open vSwitch系列之数据结构解析深入分析ofpbuf

上一篇我们分析了hmap,hamp可以说是Open vSwitch中基石结构,很多Open vSwitch中数据结构都依赖hmap。本篇我们来分析一下ofpbu...

3788

扫码关注云+社区

领取腾讯云代金券