Я помещаю превосходный ответ JLBorges на аналогичный вопрос дословно из cplusplus.com, так как это наиболее краткое объяснение, которое я прочитал по этому вопросу.
] В шаблоне, который мы пишем, есть два типа имен, которые можно использовать - зависимые имена и не зависимые имена. Зависимое имя - это имя, которое зависит от параметра шаблона; неизменяемое имя имеет то же значение, независимо от параметров шаблона.
Например:
template< typename T > void foo( T& x, std::string str, int count ) { // these names are looked up during the second phase // when foo is instantiated and the type T is known x.size(); // dependant name (non-type) T::instance_count ; // dependant name (non-type) typename T::iterator i ; // dependant name (type) // during the first phase, // T::instance_count is treated as a non-type (this is the default) // the typename keyword specifies that T::iterator is to be treated as a type. // these names are looked up during the first phase std::string::size_type s ; // non-dependant name (type) std::string::npos ; // non-dependant name (non-type) str.empty() ; // non-dependant name (non-type) count ; // non-dependant name (non-type) }
То, что зависит от зависимого имени, может быть чем-то другим для каждого конкретного экземпляра шаблона. Как следствие, шаблоны C ++ подвержены «двухфазному поиску имен». Когда шаблон сначала анализируется (до того, как выполняется какое-либо создание), компилятор просматривает не зависящие имена. Когда происходит конкретное создание шаблона, параметры шаблона известны к тому времени, и компилятор ищет зависимые имена.
На первом этапе анализатор должен знать, является ли зависимое имя именем типа или имени не-типа. По умолчанию зависимым именем считается имя не-типа.
Использовать ключевое слово typename только в объявлениях шаблонов и определениях, приведенных ниже.
blockquote>у вас есть квалифицированное имя, которое относится к типу и зависит от параметра шаблона.
Обычно, я заменяю рекурсивный алгоритм итеративным алгоритмом путем продвижения параметров, которые обычно передавались бы рекурсивной функции на стек. На самом деле Вы заменяете стопку программы одним собственным.
Stack<Object> stack;
stack.push(first_object);
while( !stack.isEmpty() ) {
// Do something
my_object = stack.pop();
// Push other objects on the stack.
}
Примечание: если у Вас есть больше чем один рекурсивный вызов внутри, и Вы хотите сохранить порядок вызовов, необходимо добавить их в обратном порядке к стеку:
foo(first);
foo(second);
должен быть заменен
stack.push(second);
stack.push(first);
Редактирование: Стопки статьи и Устранение Рекурсии (или Резервный канал Статьи ) вдаются в большее количество подробностей об этом предмете.
Таким образом, у меня просто был вопрос об интервью, и существует рекурсивное и повторяющееся решение. Вопрос, учитывая список целых чисел, как узнать, можно ли получить доступ к элементу, который имеет значение 0:
[1, 3, 4, 3, 2] => false (because no 0 is present)
[1, 3, 4, 0, 2] => false (because you can't reach the 0)
[1, 1, 1, 1, 0] => true (true because you can reach the 0)
, таким образом, необходимо запустить в 0th элементе, и можно переместить это много мест налево или право, не выходя за пределы границ измерения массива.
вот эти два решения.
Этот повторяющийся :
export const canGetZeroNonRecursive = (l: Array<number>) => {
const stk = [], s = new Set();
stk.push(0);
while(stk.length > 0){
const v = stk.pop();
if (s.has(v)) {
continue;
}
s.add(v);
const val = l[v];
if(val === 0){
return true;
}
if(v - val >= 0){
stk.push(v - val);
}
if(v + val < l.length){
stk.push(v + val);
}
}
return false;
};
этот рекурсивный :
export const canGetZero = (l: Array<number>, v: number, s: Set<number>) => {
if (s.has(v)) {
return false;
}
s.add(v);
const val = l[v];
if (val === 0) {
return true;
}
if (v - val >= 0) {
let b = canGetZero(l, v - val, s);
if (b) {
return true;
}
}
if (v + val < l.length) {
let b = canGetZero(l, v + val, s);
if (b) {
return true;
}
}
return false;
};
console.log(
canGetZero([1, 3, 2, 1, 1, 1, 0], 0, new Set<number>())
);
console.log(
canGetZeroNonRecursive([1, 3, 2, 1, 1, 1, 0])
);
повторяющееся более хорошо, так как Вам не нужно как много строгих входных параметрических усилителей.
получают код отсюда: https://github.com/ORESoftware/tesract/blob/master/src/digit-transactions.ts
Я просто upvoted ответ, предлагающий использовать явный стек, что я думаю, являюсь правильным решением и общей применимости.
я подразумеваю, что можно использовать его для преобразования любой рекурсивной функции в повторяющуюся функцию. Просто проверьте, какие значения сохраняются через рекурсивные вызовы, те - те, которые имеют , чтобы быть локальными для рекурсивной функции и заменить вызовы циклом, где Вы продвинете их на стеке. Когда стек пуст, рекурсивная функция была бы завершена.
я не могу сопротивляться, чтобы сказать, что доказательство, что каждая рекурсивная функция эквивалентна повторяющейся функции на различном типе данных, это - одна из моей самой дорогой памяти моих Университетских времен. Это было курсом (и преподаватель), который действительно заставил меня понять то, о чем было программирование.
Один шаблон для поиска является вызовом рекурсии в конце функции (так называемая хвостовая рекурсия). Это может легко быть заменено некоторое время. Например, функциональное нечто:
void foo(Node* node)
{
if(node == NULL)
return;
// Do something with node...
foo(node->left);
foo(node->right);
}
концы с вызовом к нечто. Это может быть заменено:
void foo(Node* node)
{
while(node != NULL)
{
// Do something with node...
foo(node->left);
node = node->right;
}
}
, который устраняет второй рекурсивный вызов.
Ищите Google "Стиль передачи продолжения". Существует общая процедура преобразования в хвост рекурсивный стиль; существует также общая процедура бросающихся наутек рекурсивных функций в циклы.
Стремитесь выполнить свой рекурсивный вызов Хвостовая рекурсия (рекурсия, где последний оператор является рекурсивным вызовом). Как только Вы имеете, это, преобразовывая его в повторение вообще симпатично легкий.
Ну, в целом рекурсии можно подражать как повторение путем простого использования переменной устройства хранения данных. Обратите внимание, что рекурсия и iteraction вообще эквивалентны; можно почти всегда преобразовываться в другой. Рекурсивная функция хвоста очень легко преобразовывается в повторяющуюся. Просто сделайте переменную аккумулятора локальной и выполните итерации вместо, рекурсивно вызывают. Вот пример в C++ (C, если бы не использование параметра по умолчанию):
// tail-recursive
int factorial (int n, int acc = 1)
{
if (n == 1)
return acc;
else
return factorial(n - 1, acc * n);
}
// iterative
int factorial (int n)
{
int acc = 1;
for (; n > 1; --n)
acc *= n;
return acc;
}
Знание меня, я, вероятно, сделал ошибку в коде, но идея там.
Действительно, наиболее распространенный способ сделать это состоит в том, чтобы сохранить Ваш собственный стек. Вот рекурсивная функция quicksort в C:
void quicksort(int* array, int left, int right)
{
if(left >= right)
return;
int index = partition(array, left, right);
quicksort(array, left, index - 1);
quicksort(array, index + 1, right);
}
Вот то, как мы могли сделать его повторяющимся путем хранения нашего собственного стека:
void quicksort(int *array, int left, int right)
{
int stack[1024];
int i=0;
stack[i++] = left;
stack[i++] = right;
while (i > 0)
{
right = stack[--i];
left = stack[--i];
if (left >= right)
continue;
int index = partition(array, left, right);
stack[i++] = left;
stack[i++] = index - 1;
stack[i++] = index + 1;
stack[i++] = right;
}
}
, Очевидно, этот пример не проверяет границы стека..., и действительно Вы могли измерить стек на основе худшего случая, данного оставленным и и правильные значения. Но Вы получаете идею.