Что делает «возврат» в этой функции рекурсивных комбинаций? - PullRequest
Новая
       44

Что делает «возврат» в этой функции рекурсивных комбинаций?

1 голос
/ 15 февраля 2020

Я перебирал эту функцию снова и снова в Chrome отладчике и до сих пор не могу понять, что делает return a. Спасибо за помощь!

Вот несколько уточнений: я понимаю первый раунд. Анонимная функция вызывается со следующими параметрами:

active = "", rest = "ab c", a = []

Затем вызывается сама til rest пусто, когда он заполняет массив a:

active = "ab c", rest = "", a = ["ab c"]

В этот момент мы достигаем return a, и отладчик переходит ко второму вызову fn в операторе else вместо первого оператора if. Параметры уже выглядят так:

active = "ab", rest = "c", a = ["ab c"]

This это та часть, которую я совсем не понимаю. Я знаю, что рекурсия заканчивается, только когда active и rest пустые, но после return a операторы if даже не проверяются в отладчике, он просто выделяет упомянутый второй вызов функции, и в этот момент " c "уже присвоен rest. Я предполагаю, что причина, почему эта функция не производит дубликаты, также лежит здесь, но это может быть другой вопрос, если нет. В любом случае, еще раз спасибо за помощь! 

combinations("abc");

function combinations(str) {
    var fn = function(active, rest, a) {
        if (!active && !rest)
            return;
        if (!rest) {
            a.push(active);
        } else {
            fn(active + rest[0], rest.slice(1), a);
            fn(active, rest.slice(1), a);
        }
        return a;
    }
    return fn("", str, []);
}

Ответы [ 2 ]

0 голосов
/ 16 февраля 2020

Хотя я понимаю, что этот вопрос в первую очередь касается того, как работает эта конкретная рекурсивная реализация (и на это уже есть отличный ответ!), Я думаю, стоит отметить, что это странная реализация, и что-то вроде этого, вероятно, чище: 

const combinations = (str, active = '') => 
  str .length == 0
    ? active .length == 0
      ? []
      : [active]
    : [
        ... combinations (str .slice (1), active + str [0]),
        ... combinations (str .slice (1), active)
      ]

console .log (combinations ('abc'))
0 голосов
/ 15 февраля 2020

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

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

function combinations(str) {
    var fn = function(active, rest, a) {
        if (!active && !rest) {
            // base case #1 - implicit return, no recursive call
        } else if (!rest) {
            // base case #2 - implicit return, no recursive call
            a.push(active);
        } else {
            // recursive case, where function is called again
            // (the object "a" is modified in recursion;
            //  result of recursion not directly used)
            fn(active + rest[0], rest.slice(1), a);
            fn(active, rest.slice(1), a);
        }
    }

    var o = [];     // only one output object created..
    fn("", str, o); // ..mutated..
    return o;       // ..and returned to caller.
}

Тогда должно быть легко заметить, что передача "a" в рекурсивную функцию не нужна (ie. доступ к «o» во включающей области видимости), поскольку нет нового объекта, назначенного «a» после создания исходного массива результатов.

Существует небольшая разница в перезаписи, которая (более правильно) вернет пустой массив для пустой входной строки.

...