Закрытие с рекурсивным JavaScript

//reverse a string with recursion and a closure
 function r(str){
 var i = str.length-1,results=[],j=0;
 function _r(str){
 if(i===0){
 return results.join('') + str[0];
 }
 console.log('i = ' + i);
 results[j] = str[i];
 i--,j++;
 console.log('j = ' + j); 
 return _r(str); 
 }

 return _r(str);
 }

У меня есть два вопроса о вышеуказанном коде:

  1. делает ли приведенный выше код нарушением (показывает мое невежество) безгражданность программирования функций?
  2. что, если str была большой строкой, эта реализация медленнее/интенсивнее, чем решение, которое не использовало закрытие?
1 ответ

Да, вы не используете функциональную парадигму.

В вашем случае вы используете рекурсию только для цикла, и обработка выполняется с использованием переменных, которые находятся вне функции. Это действительно не сильно отличается от использования глобальных переменных (кроме того, что они не являются глобальными, а локалями внешней функции).

Чтобы отменить строку, используя функциональный подход, вы должны учитывать, что обратная сторона строки состоит из last_char + (обратная сторона средней части) + first_char. Это определение естественным образом распространяется на рекурсивную функцию... например:

function rev(str) {
 if (str.length < 2) {
 // Empty string or a single char... reverse = input
 return str;
 } else {
 return str[str.length-1] + rev(str.slice(1, -1)) + str[0];
 }
}

это не использует явное состояние (как вы можете заметить, никаких назначений вообще нет).

Если вы ищете оптимизированную версию tail-call, рассмотрите:

function rev(todo, done) {
 if (todo === "") {
 return done;
 } else {
 return rev(todo.slice(1), todo[0] + (done||""));
 }
}

идея в этом случае заключается в том, что в случае обработки должен быть return (в предыдущем примере это не происходит, потому что результат рекурсии добавляется по одному символу на каждый конец перед возвратом).

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

Наконец, это еще одна версия, а не просто функциональная, но похоже на то, что вы пытаетесь:

function rev(str) {
 function rev1(v, i, j) {
 if (i >= j) {
 return v.join("");
 } else {
 var t=v[i]; v[i]=v[j]; v[j]=t;
 return rev1(v, i+1, j-1);
 }
 }
 return rev1(str.split(""), 0, str.length-1);
}

Это не чисто функционально, потому что векторные элементы меняются местами (и вы можете видеть, что есть назначения), но использует оптимизированную рекурсию хвоста для выполнения цикла. Обратите внимание, что rev1 не является закрытием, а функцией (не фиксирует состояние, и вы также можете вывести его за пределы rev).

licensed under cc by-sa 3.0 with attribution.