• Subject: Re: Functional programming (was Re: Default value in function parameters?)
• From: Luis Carvalho <carvalho@...>
• Date: Thu, 21 Sep 2006 21:50:17 -0400

```> Fib = Memoise(function(n)
>   return Fib(n-1) + Fib(n-2)
> end)
> Fib[1] = 1
> Fib[2] = 1
>
> = Fib[200]
>
> The definition of Memoise I use has been left abandoned on the Lua Wiki
> at http://lua-users.org/wiki/FuncTables since January 17, 2003 :) so I
> won't bother repeating it here.
>
> By the way, the above example won't work with values larger than
> 200 unless you recompile Lua with a larger C recursion limit
> (LUAI_MAXCCALLS in luaconf.h)

You could also avoid the C recursion limit by having a memoization scheme that
does not use functables:

func_memoize = function(f, t)
local t = t or {}
return function(k)
local v = t[k]
if v==nil then
v = f(k)
t[k] = v
end
return v
end
end

Fib = func_memoize(function(n)
return Fib(n-1) + Fib(n-2)
end, {
[1] = 1,
[2] = 1
})

= Fib(200)
2.8057117299251e+41

This might be a bit slower, though.

Cheers,
Luis.

--
A mathematician is a device for turning coffee into theorems.
-- P. Erdos

--
Luis Carvalho
Applied Math PhD Student - Brown University
PGP Key: E820854A <carvalho@dam.brown.edu>

```

• Follow-Ups: