局部函数与尾调用
2017-12-01 00:00:00


一、局部函数

我们在上一讲知道函数是一种值,是值便能使用变量承接,全局变量承接的函数是一般我们说的函数,使用局部变量承接的函数便是我们要讨论的局部函数。

局部函数的声明:

local f=function()

<block>

end

local function f()

<block>

end

和局部变量差不多,在局部函数外调用local function会报错。

简单举例:

错误举例:会显示报错,因为在局部函数外调用内嵌函数了


二、递归形式的局部函数

我们要特别注意,最后递归的时候函数是否是局部函数。

我们以fact为例,首先列举一个错误的例子。

image.png

以上例子语法没有错误,但是运行报错。原因是递归函数fact(n-1)调用的是全局函数fact,而我们只定义了局部函数fact,因此会报错。

为了避免这种情况,可更改为以下两种形式的例子,第二个的例子会更简便。

image.png


image.png

三、尾调用

在函数的最后动作是调用最后一个函数的时候,我们称之为尾调用。

例如:

function f(x)

  return g(x)

end

因为,当f调用完g之后就再无其他事情可做了。因此在这种情况下,程序就不需要返回那个“尾调用”所在的函数了。所以在“尾调用”之后,程序也不需要保存任何关于该函数的栈(stack)信息了。当g返回时,执行控制权可以直接返回到调用f的那个点上。有一些语言实现(例如Lua解释器)可以得益于这个特点,使得在进行“尾调用”时不好非任何栈空间。将这种实现称为支持“尾调用消除”。

判断当前的调用是一条“尾调用”的准则:一个函数在调用完另一个函数之后,是否就无其他事情需要做了。

例如,下面的代码就不是一条“尾调用”:

 function f(x)

    g(x)

 end

这个示例的问题在于,当调用完g后,f并不能立即返回,它还需要丢弃g返回的临时结果。类似的,以下所有调用也都不符合上述准则:

 return g(x)+1  --必须做一次加法

 return x or g(x)  --必须调整为一个返回值

 return(g(x))  --必须调整为一个返回值

Lua中,只有“return <func>(<args>)”这样的调用形式才算是一条“尾调用”。Lua会在调用前对<func>及其参数求值,所以它们可以是任意复杂的表达式。举例来说,下面调用就是一条“尾调用”:

 return x[i].f(x[j]+a*b,i+j)

四、[“尾调用”迷宫游戏示例]

 “尾调用类似一条goto语句。在Lua尾调用已答应永久是编写“状态机(state machine)”。这种程序通常以一个函数来表示一个状态,改变状态就是goto(或调用)到另一个特定的函数。举一个简单的迷宫游戏的例子来说明这个问题。例如,一个迷宫有几间房间,每间房间中最多有东南西北4扇门。用户在每一步移动中都需要输入一个移动的方向。如果在某个方向上有门,那么用乎可以进入相应的房间;不然,程序就打印一条警告。游戏目标就是让用户从最初的房间走到最终的房间。

这个游戏就是一种典型的状态机,其中当前房间就是一个状态。可以将迷宫中的每间房间实现为一个函数,并使用“尾调用”来实现从一件房间移动到另一间房间。在以下代码中,实现一个具有4间房间的迷宫:

function room1 ()

    local move = io.read()

    if move == "sourth" then return room3()

    elseif move == "east" then return room2()

    else

        print("invalid move")

        return room1()  -- stay in the same room

    end

end

function room2()

    local move = io.read()

    if move == "sourth" then return room4()

    elseif move == "west" then return room1()

    else

        print("invalid move")

        return room2()

    end

end

function room3()

    local move = io.read()

    if move == "north" then return room1()

    elseif move == "east" then return room4()

    else

        print("invalid move")

        return room3()

    end

end

function room4()

    print("congratulations!")

end