Инвертировать строку: рекурсия против итерации в JavaScript

Question

один месяц назад я давал интервью некоторым членам Google PTO.Один из вопросов был: Рекурсивно инвертировать строку в js и объяснить время выполнения большими буквами O

Это было мое решение:

function invert(s){
    return (s.length > 1) ? s.charAt(s.length-1)+invert(s.substring(0,s.length-1)) : s;
}

Довольно просто,Я думаю.

И по поводу биг-о записи я быстро ответил O (n), так как время работы линейно зависит от входа.- Молчание - а потом, он спросил меня, каковы различия с точки зрения времени выполнения, если вы реализуете его итерацией?

Я ответил, что иногда компилятор "переводит" рекурсию в итерацию (некоторые курсы языка программированиявоспоминания), поэтому нет никаких различий в отношении итерации и рекурсии в этом случае.Кстати, поскольку у меня не было отзывов об этом конкретном вопросе, и интервьюер не ответил «хорошо» или «нет», я хотел бы знать, можете ли вы согласиться со мной или вы можете объяснить мне, могут ли быть различия в2 вида реализации.

Большое спасибо и С уважением!

Answer 1

Ваше решение выглядит O ( n ²) для меня. Вызов substring, скорее всего, O ( n ) - типичная реализация выделит место для новой строки, а затем скопирует подстроку. [Но см. Комментарии.] Конкатенация строк +, вероятно, также будет O ( n ). Может даже случиться, что length - это O ( n ), но я думаю, что это маловероятно.

---

Вы выдвинули идею, что компилятор может преобразовать рекурсию в итерацию. Это правда, но это редко реализуется вне функциональных языков и Scheme; и, как правило, единственным применяемым преобразованием является устранение хвостовой рекурсии . В вашем коде рекурсия не находится в хвостовой позиции : после рекурсивного вызова invert вам все еще нужно вычислить +. Таким образом, устранение хвостовой рекурсии не относится к вашему коду.

Это означает, что итеративная версия invert должна быть реализована другим способом. Он может иметь ту же или другую сложность, мы не можем сказать, пока не увидим его.

Answer 2

С другой стороны, чтобы использовать хвостовую рекурсию, которая позволяет компилятору реализовать вашу рекурсию в виде цикла, вы не можете оставить состояние в стеке.Чтобы обойти это, вы можете передать «состояние» в качестве дополнительного параметра вашей функции:

function invert(sofar, s)
{
    return (s.length > 0) ? invert(s.charAt(s.length-1)+sofar, s.substring(0,s.length-1)) :  sofar;
}