Ханойские башни итеративная функция - PullRequest
Новая
       6

Ханойские башни итеративная функция

1 голос
/ 16 марта 2011

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

Вот моя функция ... 

Create function fnuHanoi (@Nro int)
returns int
as
begin
Declare @Result int
If @Nro = 1
Set @Result = 1
else
Set @Result = (((dbo.fnuHanoi(@Nro-1))*2)+1)
return @Result
end
go

Я пробовал что-то подобное ... 

Create function fnuHanoi (@Nro int)
returns int
as
begin
Declare @Discs int
Declare @i int
Set @Discs = 1
Set @i = 1
while (@Discs <= @Nro)
begin
    Set @i = (@i * 2) + 1       
end
return @i
end
go

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

1 Ответ

3 голосов
/ 16 марта 2011

Я не знаком с синтаксисом SQL, поэтому я просто попытаюсь объяснить как можно лучше.

В случае линейной рекурсии, как этот (т.е. только один рекурсивный вызов за раз), способ перевести его в итеративную функцию, чтобы думать наоборот рекурсивным стилем.Вместо того чтобы начать с Nro и перейти к 1, вы можете начать с 1 и перейти к Nro.

Таким образом, в итерационном методе result начинается с 1. Затем вы можете выполнять итерацию из2 до нро.В каждой итерации вы удваиваете результат, а затем добавляете один.

Вот еще одна возможная перспектива.В рекурсивном стиле у вас есть Nro число вызовов вложенных функций.Когда завершается самый глубокий (то есть, когда Nro равен 1), может завершиться следующий восходящий (когда Nro равен 2), а затем следующий, и он продолжает всплывать, пока вы не вернетесь к исходному вызову.Итерационный метод следует за пузырящимся поведением (насколько порядок вычислений идет).Барботирование начинается с 1 - итерация тоже.Пузырьки также заканчиваются в Nro, точно так же, как итерации.

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

...