one month ago I've been interviewed by some google PTO members. Один из вопросов был: Инвертируйте строку рекурсивно в js и объясните время выполнения в нотации big O
вот мое решение:
function invert(s){
return (s.length > 1) ? s.charAt(s.length-1)+invert(s.substring(0,s.length-1)) : s;
}
Довольно просто, я думаю.
А насчет обозначения big-o, я быстро ответил O(n), так как время работы линейно зависит от входных данных. - Тишина - и тут он спросил меня, какие различия в плане времени работы, если реализовать это с помощью итерации?
Я ответил, что иногда компилятор "переводит" рекурсию в итерацию (некоторые курсы языка программирования запомнились), так что в этом случае нет различий между итерацией и рекурсией. Поскольку у меня не было обратной связи по этому вопросу, и интервьюер не ответил "ok" или "nope", я хотел бы узнать, может быть, вы согласны со мной или можете объяснить мне, могут ли быть различия между этими двумя видами реализации.
Большое спасибо и с уважением!