Будет ли эта программа завершаться для каждого целого числа?

Question

В Частичном тесте для подготовки к GATE возник вопрос:

f(n):
     if n is even: f(n) = n/2
     else f(n) = f(f(n-1))

Я ответил: "Это прекратится для всех целых чисел", потому что даже для отрицательных целых чисел это прекратится как ошибка переполнения стека.

Но мой друг не согласился, сказав, что, поскольку это не реализованный код, а просто псевдокод, в случае отрицательных целых чисел это будет бесконечная рекурсия.

Изменить: была небольшая проблема в коде ..

Какой ответ правильный и почему?

Answer 1

Этот псевдокод в том виде, в котором он был задан , завершится для всех целых чисел. Если дано нечетное целое число, оно вычтет одно из него и вернется к измененному значению; для четных целых он делится на 2, но не рекурсивно. Поскольку функция возвращается с четным числом в качестве параметра при первоначальном вводе нечетного числа, она будет повторяться не более одного раза, а затем возвращаться.

(Примечание: код, который изначально был указан на момент публикации, был f(x) = f(x-1) для нечетного x.)

В новой редакции оно будет прекращено для всех неотрицательных целых чисел. Тем не менее, он не завершится для всех отрицательных целых чисел; в частности, f(-1) является неопределенным вызовом.