Дана рекурсивная функция на языке Python:
def f(s):
if len(s) <= 2:
return s
return f(s[1:-1]) + s[-1] + s[0]
Сколько всего раз вызывается функция f (считая первый вызов) при выполнении f("ABCDEFG") и какое значение возвращает этот вызов?
Показать ответ и разборСкрыть ответ и разбор
Верный ответ
- A4 вызова; DECFBGA
Разбор
Срез s[1:-1] отбрасывает первый и последний символы. Цепочка вызовов: f("ABCDEFG") -> f("BCDEF") -> f("CDE") -> f("D"). На строке "D" длина 1 (не больше 2), поэтому рекурсия заканчивается: всего 4 вызова. Возврат: f("D") = "D"; f("CDE") = "D" + "E" + "C" = "DEC"; f("BCDEF") = "DEC" + "F" + "B" = "DECFB"; f("ABCDEFG") = "DECFB" + "G" + "A" = "DECFBGA". Итого «4 вызова; DECFBGA». Вариант «DCEBFAG» получается при неверном порядке s[0] + s[-1], «GAFBECD» — при добавлении символов перед результатом рекурсии, а «3 вызова» не учитывает вызов на базовом случае.