As linguagens de programação são responsáveis por tirar do papel os algoritmos criados pelo programador e por transformá‑los em programas para serem executados pelos computadores m

Gabarito

Certo

Comentário do professor

A afirmação é correta porque em Java a recursão consiste em um método recursivo chamar a si mesmo repetidamente até encontrar uma condição de parada. Sem essa condição o programa entra em loop e pode ocorrer estouro de pilha.

Na busca binária o problema é dividido reduzindo o intervalo pela metade a cada chamada, isto é, \(n \to n/2\), o que gera complexidade típica \(O(\log n)\). Cada chamada recursiva trata uma subfaixa do array ordenado até localizar o elemento ou concluir que não existe.

Em algoritmos de divisão e conquista como o merge sort, o array é quebrado em subproblemas menores, cada um resolvido recursivamente e então combinados. A recorrência típica é \(T(n)=2T(n/2)+O(n)\), resultando em \(O(n\log n)\).

Portanto, recursão em Java é apropriada e amplamente usada nesses casos, desde que haja uma condição de parada bem definida e controle do custo de chamadas.