Как сделать рекурсивный реверс строки?

#javascript #задание_на_собеседовании

Решаю задачи, которые задают на собеседовании.  


  Требуется : написать рекурсивную функцию, которая переворачивает строку.


Самостоятельно решил двумя отличными друг от друга способами, но какой из них предпочтительней
и почему без Вашей помощи определить не смогу.  

И был бы рад увидеть более оптимальные варианты.

I способ : 



function repl_str(str) {
  if (typeof str == "string")
    str = {
      str: str,
      index: 0,
      buff: ""
    };
  else if (str.index >= str.str.length) return str.buff;

  str.buff += str.str.substring(str.str.length - (str.index + 1), str.str.length
- str.index);
  str.index++;

  return repl_str(str);
}
console.log(repl_str("test")); //tset




II способ : 



function repl_str(str, stack) {
  if (typeof stack == "undefined") {
    stack = {};
    stack.index = 0;
    stack.buff = "";
  } else if (stack.index >= str.length) return stack.buff;

  stack.buff += str.substring(str.length - (stack.index + 1), str.length - stack.index);
  stack.index++;
  return repl_str(str, stack);
}

console.log(repl_str("test")); //tset



    

Ответы

Ответ 1

как-то так наверное хотелось

function r(a) {
 return a === '' ? '' : r(a.slice(1)) + a[0];
}


без slice: 

function r(a,n) {
 n = typeof n === 'undefined' ? a.length - 1 : n - 1;
 return n >= 0 ? a[n] + r(a, n) : '';
}


но последняя какая-то глупая рекурсия. 

для slice варианта придумал "оптимизацию" (-1 вызов) 

function r(a) {
  return a.length - 1 ? r(a.slice(1)) + a[0] : a;
};


ES6:

const r = (a) => a.length - 1 ? r(a.slice(1)) + a[0] : a;


подсмотрел такой хак для рекурсии на стрелочных функциях

(
  (
    a,
    r = (a) => a.length-1 ? r(a.slice(1)) + a[0] : a // дефолтный параметр r
  ) => r(a)
)("abcdef");


чет я тогда забыл про reverse: :)

"12345".split('').reverse().join('');


Ответ 2

Можно так например.

function r(s){return s.length == 0 ? s : r(s.substring(1)).concat(s.charAt(0));}


UPD: Отрефакторил в однострочник.

Раскрытие рекурсии:

r("Лезу в узеЛ")
(r("Лезу в узе")) + "Л"
((r("Лезу в уз")) + "е") + "Л"
(((r("Лезу в у")) + "з") + "e") + "Л"
((((r("Лезу в ")) + "у") + "з") + "e") + "Л"
(((((r("Лезу в")) + " ") + "у") + "з") + "e") + "Л"
((((((r("Лезу ")) + "в") + " ") + "у") + "з") + "e") + "Л"
(((((((r("Лезу")) + " ") + "в") + " ") + "у") + "з") + "e") + "Л"
((((((((r("Лез")) + "у") + " ") + "в") + " ") + "у") + "з") + "e") + "Л"
(((((((((r("Ле")) + "з") + "у") + " ") + "в") + " ") + "у") + "з") + "e") + "Л"
((((((((((r("Л")) + "e") + "з") + "у") + " ") + "в") + " ") + "у") + "з") + "e") + "Л"


А вот собственно симметричный вариант, говорят что он в два раза медленее асимметричного:

function r(s) {
  if (s.length < 2)
    return s;
  var halfIndex = Math.ceil(s.length / 2);
  return r(s.substr(halfIndex)) + r(s.substr(0, halfIndex));
}


Ответ 3

А почему ещё никто не предложил хвостовую рекурсию? Хей, js же функциональный язык!

function r(s) {
    function r1(s, tail) {
        return s === '' ? tail : r1(s.substring(1), s[0] + tail);
    }
    return r1(s, '');
}




function r(s) {
    function r1(s, tail) {
        return s === '' ? tail : r1(s.substring(1), s[0] + tail);
    }
    return r1(s, '');
}

function doit() {
    $('#r').text( r ($('#i').val()) );
}
$(':button').click(doit);
doit();







Result: 



Ответ 4

Как вариант -  

function reverce(string) {
    var length = string.length == 1 ? 0 : string.length;
    var result = '';

    while (length--) {
        result += reverce(string[length]);

        if (length == 0) {
            string = result;
        }
    }

    return string;
}


И тест -   



'use strict';

const REPEAT = 5;
const ITERATION = 100000;

var body = document.getElementsByTagName('body')[0];

function getP(){
	return document.createElement('p');
}


function runTest(callback){
	var repeat = REPEAT;

	while(repeat-- > 0)
	{
		var result = speed(callback);
		var p = getP();
		p.innerHTML = result;
		body.appendChild(p);

		console.log(result);
	}
}


function speed(callback){

	var startTime = new Date();
	for (var z = 0; z < ITERATION; z++) {
		callback();
	}

	var finishTime = new Date();
	return 'Время выполнения - ' + (finishTime.getTime() - startTime.getTime()) + '.' 
}

// runTest();

console.log('===== start =====');

var p = getP();
p.innerHTML = '### TEST - 1';

body.appendChild(p);

runTest(one);

function one(){

	repl_str('some text');

	function repl_str(str)
	{
	    if (typeof str == "string")
	        str = { str: str, index: 0, buff: "" };
	    else if (str.index >= str.str.length) return str.buff;

	    str.buff += str.str.substring(str.str.length - (str.index + 1), str.str.length
- str.index);
	    str.index++;

	    return repl_str(str);
	}
}

console.log('===== start =====');

var p = getP();
p.innerHTML = '### TEST - 2';

body.appendChild(p);
runTest(two);

function two(){

	repl_str('some text');

	function repl_str(str, stack)
	{
	    if (typeof stack == "undefined")
	    {
	        stack = {};
	        stack.index = 0;
	        stack.buff = "";
	    } else if (stack.index >= str.length) return stack.buff;

	    stack.buff += str.substring(str.length - (stack.index + 1), str.length - stack.index);
	    stack.index++;
	    return repl_str(str, stack);
	}
}

console.log('===== start =====');

var p = getP();
p.innerHTML = '### TEST - 3';

body.appendChild(p);
runTest(three);

function three(){

	reverce('some text');

	function reverce(string) {
		    var length = string.length == 1 ? 0 : string.length;
		    var result = '';
	
		    while (length--) {
		        result += reverce(string[length]);
	
		        if (length == 0) {
		            string = result;
		        }
		    }
	
		    return string;
		};
}
console.log('=================');


Ответ 5

Попробуйте так:

const reverse = a => a.length === 0 
? [] 
: [ a[a.length - 1], ...reverse(a.slice(0, a.length - 1)) ];


Ответ 6

Наглядный вариант, итеративный процесс.

const revers = (str) => {
  const lastIndex = str.length - 1;

    const iter = (i, acc) => {
      if(i > lastIndex) return acc;
      return iter(i + 1, `${str[i]}${acc}`)
    }

  return iter(0, '');
};


Ответ 7

Ну или например

const reverse = (str) => {
    let result = '';
    for (let i = str.length - 1; i >= 0; i--)
        result += str[i];
    return result;
}