Оптимизация рекурсивной функции

В настоящее время я работаю над побочным проектом, который имеет дело с большим количеством рекурсивных вызовов. Я не ученый-компьютерщик, поэтому я не совсем уверен, как оптимизировать свой код. Я знаю, что рекурсивные функции не очень эффективны, и я слышал, что вы часто можете заменить их хвостовыми вызовами, но я не совсем уверен, как это сделать. Эта функция принимает три массива: appendList, sequence и used. Другие аргументы, база, длина, индекс и последнее слово являются целыми числами.

function Recursion(appendList, base, length, sequence, used, lastWord, index)
#Global variables:
global G_Seq_List
global G_Seq_Index

used = ones(UInt8, 1, base^length)
used[1] = 0

if index == base^length
    check = zeros(UInt8, base^length, 1)

    for i = 1 : base^length
        index = 1
        for j = 1 : length
            k = mod(i+j-1,base^length)
            index = index + base^(length - j)*sequence[k+1] 
        end

        check[index] = check[index] + 1

        if check[index] != 1 
            return
        end
    end

    G_Seq_List[G_Seq_Index,:] = sequence[:] 
    G_Seq_Index = G_Seq_Index + 1 

    return
end

#Builds Sequence
for i = 1 : base^length
    if appendList[i , mod(lastWord - 1, base^(length - 1)) + 1] == 1
        if used[i] == 1 
            tempUsed = used
            tempUsed[i] = 0
            tempCounter = index + 1 
            tempSequence = sequence
            tempSequence[tempCounter] = mod(i - 1, base)
            Recursion(appendList, base, length, tempSequence, tempUsed, i, tempCounter)
        end
    end
end
end

Можно ли быстро превратить эту рекурсию в хвостовой вызов? Если нет, что я могу сделать, чтобы оптимизировать эту функцию?


optimization recursion tail-recursion
person RedShift    schedule 26.04.2017    source источник
comment
Можете ли вы также объяснить, что вы пытаетесь выполнить с помощью этой функции? Кроме того, первым шагом в оптимизации является понимание того, почему вы хотите оптимизировать. Это медленно? Каков типичный размер ввода?   -  person justhalf    schedule 27.04.2017

Ответы (1)


arrow_upward
5
arrow_downward

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

«Оптимизация хвостового вызова» — это то, что делают компиляторы (или среды выполнения), которые автоматически преобразуют рекурсию в цикл, если рекурсивный вызов является последним вызовом в функции (отсюда и название — «хвост call"), как правило, путем повторного использования одного и того же кадра вызова вместо выделения нового. Повторное использование фрейма допустимо, поскольку, если все, что вы делаете с результатом рекурсивного вызова, это возвращаете его, вам больше ничего не нужно из вызова объемлющей функции, так что в первую очередь нет причин оставлять фрейм живым.

Итак, что вам нужно проверить:

  1. Поддерживает ли ваш компилятор оптимизацию хвостового вызова.
  2. Что вам нужно сделать, чтобы позволить компилятору сделать это — обычно работает простой шаблон return f(...), но иногда компилятор может поддерживать более сложный код.

Оба зависят от вашего конкретного компилятора, поэтому я бы посмотрел документацию об этом - я не мог сказать, что это такое, из вашего вопроса.

person Oak    schedule 27.04.2017