Будет ли эта программа завершена для каждого целого числа?
В Частичном тесте для подготовки к GATE возник вопрос:
f(n):
if n is even: f(n) = n/2
else f(n) = f(f(n-1))
Я ответил: "Это прекратится для всех целых чисел", потому что даже для отрицательных целых чисел это прекратится как ошибка переполнения стека.
Но мой друг не согласился, сказав, что, поскольку это не реализованный код, а просто псевдокод, в случае отрицательных целых чисел это будет бесконечная рекурсия.
Изменить: была небольшая проблема в коде..
Какой ответ правильный и почему?
1 ответ
Этот псевдокод в том виде, в котором он был задан изначально , завершится для всех целых чисел. Если дано нечетное целое число, оно вычтет одно из него и вернется к измененному значению; для четных целых он делится на 2, но не рекурсивно. Поскольку функция возвращается с четным числом в качестве параметра при первоначальном вводе нечетного числа, она будет повторяться не более одного раза, а затем возвращаться.
(Примечание: код, который изначально был указан на момент публикации, был f(x)=f(x-1) для нечетного x.)
Как исправлено, это прекратится для всех неотрицательных целых чисел. Тем не менее, он не завершится для всех отрицательных целых чисел; особенно, f(-1) является неопределенным вызовом.