Почему сверху вниз и снизу вверх работают по-разному в моем коде Lua?

Question

Я делаю код динамической программы. Речь идет о поиске наименьшего числа вычислений тремя способами: делить на 3, делить на 2 или вычитать от 1 до заданного числа, чтобы сделать его 1.

Во-первых, я сделал функцию «один» сверху вниз. Но когда я добавляю 1 000 000, это приводит к переполнению стека.

Во-вторых, я сделал функцию «два» снизу вверх. Работает с вводом 1 000 000 скважин.

local num = io.read("*n")

local memo = {
    [0] = 0,
    [1] = 0
}

function one(n)
    if memo[n] == nil then
        if n % 3 == 0 then
            memo[n] = 1 + math.min(one(n-1), one(n//3))
        elseif n % 2 == 0 then
            memo[n] = 1 + math.min(one(n-1), one(n//2))
        else
            memo[n] = 1 + one(n-1)
        end
    end
    return memo[n]
end

local last = 1

function two(n)
    if memo[n] == nil then
        for i = last + 1, n do
            if i % 3 == 0 then
                memo[i] = 1 + math.min(two(i-1), two(i//3))
            elseif i % 2 == 0 then
                memo[i] = 1 + math.min(two(i-1), two(i//2))
            else
                memo[i] = 1 + two(i-1)
            end
        end
        last = n
    end
    return memo[n]
end



print(two(num))

Я не знаю, почему это произошло. Разве это не работает так же тихо?

Answer 1

Вы получаете переполнение стека сверху вниз, потому что нижние числа не определены.

Давайте пройдем через обе функции, если мы введем 5, я добавил строки печати в код, чтобы проиллюстрировать, каккод работает.

---

Я начну с функции два.

Undefined: 5 -- This is the first call.
Undefined: 2  -- first value once in the for loop.
%2: 2         -- Enter mod 2 block.
Defined: 1    -- Second call. (now 2 calls deep)
Defined: 1    -- Third call. (still 2 calls deep)
Undefined: 3  -- Next  value in First calls for loop. (back to 1 deep)
%3: 3         -- Enter mod 3 block.
Defined: 2    -- Forth call. (now  2 calls deep)
Defined: 1    -- Fifth call. (still 2 calls deep)
Undefined: 4  -- Next  value in First calls for loop. (back to 1 deep)
%2: 4         -- Enter mod 4 block.
Defined: 3    -- Sixth call. (now 2 calls deep)
Defined: 2    -- Seventh call. (still 2 calls deep)
Undefined: 5  -- Next  value in First calls for loop. (back to 1 deep)
else: 5       -- Enter else block.
Defined: 4    -- Eighth call. (still 2 calls deep)
3             -- return from initial call.

Как вы можете видеть каждую итерацию цикла как предыдущие значения, уже определенные, так что они возвращаются немедленно, и он не выполняет рекурсию более чем на 2 глубоких вызова.

---

Вот вывод для функции один:

Undefined: 5 -- This is the first call.
else: 5      -- Enter the else block.
Undefined: 4 -- Second call. (now 2 calls deep)
%2: 4        -- Enter mod 2 block.
Undefined: 3 -- Third call. (now 3 calls deep)
%3: 3        -- Enter mod 3 block.
Undefined: 2 -- Forth call. (now 4 calls deep)
%2: 2        -- Enter mod 2 block.
Defined: 1   -- Fifth call. (now 5 calls deep)
Defined: 1   -- Sixth call. (still 5 calls deep)
Defined: 1   -- Seventh call. (Second call from value 3)
Defined: 2   -- Eighth call. (Second call from value 4)
3            -- return from initial call.

Здесь каждый вызов должен идти все глубже и глубже, поскольку не определены нижние значения.Это приводит к переполнению стека.

функция два на самом деле не является рекурсивной, как функция первая, вы можете просто выполнить memo[i-1] и memo[i/2], поскольку они гарантированно уже были обработаны.