В статье используется рекурсия Top Down
, так как они разбивают большие регистры на меньшие, а затем объединяют результат меньших.
В вызовах функций рекурсии они помещаются друг на друга на стек вызовов функций. Они выталкиваются либо
(1) Once the base case is reached
или
(2) Results of function calls above them in the stack has been computed and it's their turn now.
Ваш код не выполняет Bottom Up
рекурсию и также не D&C
,
Рассмотрим этот случай: -
["care", "car", "cat", "cater", "click", "clang", "core", "коралл"]
Стек Изначально: -
cor
cl
cat
car
Пока L oop Итерация # 1:
c
cat
car
Пока L oop Итерация # 2:
c
car
В то время как L oop Итерация # 3:
c
Ваш while l oop комбинирует элементы последовательно и не использует свойство D&C
, Если вы измените lo+=2
в for для l oop на lo+=1
, тогда ваш код будет таким же, как Approach 1: Horizontal scanning
.
. Однако использование очереди сделает код рекурсией Bottom-Up
. Обратите внимание, что каждый раз, когда два элемента выталкиваются, они представляют две взаимоисключающие половины, которые также были бы найдены в дереве рекурсии Top Down
подхода. Рассмотрим этот случай: -
["care", "car", "cat", "cater", "click", "clang", "core", "коралл"]
Изначально очередь: -
cor
cl
cat
car
Пока L oop Итерация # 1:
ca
cor
cl
Пока L oop Итерация # 2:
c
ca
Пока L oop Итерация № 3:
c