INEP, ENADE

A linguagem Python não permite alguns tipos de otimização como, por exemplo, a recursão em cauda e, devido à sua natureza dinâmica, é impossível realizar esse tipo de otimização em tempo de compilação tal como em linguagens funcionais como Haskell ou ML.

Disponível em: Acesso: em 15 jun. 2019 (adaptado).

O trecho de código a seguir, escrito em Python, realiza a busca binária de um elemento em uma lista x e a função tem código recursivo em cauda. lst binary_search

1 def binary_search(x, lst, low=None, high=None): 2 if low == None : low = 0 3 if high == None : high = len(lst)-1 4 mid = low + (high - low) // 2 5 if low > high :

6 return None 7 elif lst[mid] == x :

8 return mid 9 elif lst[mid] > x :

10 return binary_search(x, lst, low, mid-1) 11 else :

12 return binary_search(x, lst, mid+1, high)

Disponível em: Acesso em: 15 jun. 2019 (adaptado).

Considerando esse trecho de código, avalie as afirmações a seguir.

I. Substituindo-se o conteúdo da linha 10 por e substituindo-se o conteúdo da high = mid - 1 linha 12 por não se altera o resultado de uma busca. low = mid + 1,

II. Envolvendo-se o código das linhas 4 a 12 em um laço substituindo-se o conteúdo while True, da linha 10 por e substituindo-se o conteúdo da linha 12 por high = mid - 1 low = mid + 1 remove-se a recursão de cauda e o resultado da busca não é alterado.

III. Substituindo-se o código da linha 10 por:

newhigh = mid-1 return binary_search(x, lst, low, newhigh) e substituindo-se o código da linha 12 por:

newlow = mid+1 return binary_search(x, lst, newlow, high) remove-se a recursão de cauda.

IV. Substituindo-se o conteúdo das linhas 9 a 12 por

if lst[mid] > x :

newlow = low newhigh = mid-1 else:

newlow = mid+1 newhigh = high return binary_search(x, lst, newlow, newhigh) mantém-se o resultado da busca.

É correto o que se afirma em