Способ пойти от рекурсии до повторения

Таким образом, у меня просто был вопрос об интервью, и существует рекурсивное и повторяющееся решение. Вопрос, учитывая список целых чисел, как узнать, можно ли получить доступ к элементу, который имеет значение 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;
    }
}

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