Esse programa será finalizado para todo número inteiro?

Em um teste de peça para preparação do GATE, houve uma pergunta:

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

Eu respondi "Terminará para todos os números inteiros", porque mesmo para alguns números inteiros negativos, terminará como Erro de estouro de pilha .

Mas meu amigo discordou em dizer que, como esse código não é implementado e apenas o pseudocódigo, será uma recursão infinita no caso de alguns números inteiros negativos.

Qual resposta está correta e por quê?

A resposta correta é que essa função não termina para todos os números inteiros (especificamente, não termina em -1). Seu amigo está correto ao afirmar que esse é um pseudocódigo e o pseudocódigo não termina em um estouro de pilha. O pseudocódigo não é formalmente definido, mas a idéia é que ele faça o que é dito na lata. Se o código não indicar "terminar com um erro de estouro de pilha", não haverá erro de estouro de pilha.

Mesmo se essa fosse uma linguagem de programação real, a resposta correta ainda seria "não termina", a menos que o uso de uma pilha faça parte da definição da linguagem. A maioria das linguagens não especifica o comportamento de programas que podem sobrecarregar a pilha, porque é difícil saber com precisão a quantidade de pilha que um programa usará.

Se a execução do código em um intérprete ou compilador real causa um estouro de pilha, em muitos idiomas, é uma discrepância entre a semântica formal do idioma e a implementação. É geralmente entendido que implementações de uma linguagem farão apenas o que pode ser feito em um computador concreto com memória finita. Se o programa morrer com um estouro de pilha, você deverá comprar um computador maior, recompilar o sistema, se necessário, para suportar toda essa memória e tente novamente. Se o programa não terminar, talvez seja necessário continuar fazendo isso para sempre.

Mesmo o fato de um programa exceder ou não a pilha não está bem definido, pois algumas otimizações, como otimização de chamada de cauda e memoização, podem permitir uma cadeia infinita de chamadas de função no espaço de pilha de ligação constante. Algumas especificações de linguagem exigem que as implementações realizem otimização de chamada final sempre que possível (isso é comum em linguagens de programação funcionais). Para esta função, f(-1)expande para f(f(-2)); a chamada externa para fé uma chamada final, para que ela não empurre nada na pilha, portanto, apenas f(-2)vá para a pilha e ela retorne -1; portanto, a pilha retornará ao mesmo estado em que estava no início. Assim, com a otimização da chamada de chamada em f(-1)loop para sempre na memória constante.

Se observarmos isso em termos da linguagem C, uma implementação é livre para substituir o código pelo código que produz o mesmo resultado em todos os casos em que o original não invoca um comportamento indefinido. Para que ele possa substituir

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

com

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

Agora a implementação está autorizada a aplicar recursão de cauda:

f(n):
   while n is not even do n = (n-1) / 2
   f(n) = n/2

E isso faz um loop para sempre se e somente se n = -1.