Question

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çãotal como em linguagens funcionais como Haskell ou ML.Considerando esse trecho de código, avalie as afirmações a seguir.I. Substituindo-se o conteúdo da linha 10 por high = mid - 1 e substituindo-se o conteúdo dalinha 12 por low = mid + 1, não se altera o resultado de uma busca.II. Envolvendo-se o código das linhas 4 a 12 em um laço while True, substituindo-se o conteúdoda linha 10 por high = mid - 1 e substituindo-se o conteúdo da linha 12 por low = mid + 1remove-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-1return binary_search(x, lst, low, newhigh)e substituindo-se o código da linha 12 por:newlow = mid+1return binary_search(x, lst, newlow, high)remove-se a recursão de cauda.IV. Substituindo-se o conteúdo das linhas 9 a 12 porif lst[mid] > x :newlow = lownewhigh = mid-1else:newlow = mid+1newhigh = highreturn binary_search(x, lst, newlow, newhigh)mantém-se o resultado da busca.É correto o que se afirma emA I, apenas.B II e III, apenas.C II e IV, apenas.D I, III e IV, apenas.E I, II, III e IV.

#ENADE

Answer 1

É correto o que se afirma em : C) II e IV, apenas.

O trecho do código escrito em Python que   mantém-se o resultado da busca  binária de um elemento x em uma lista lst e a função binary_search tem código recursivo em cauda, ficaria da seguinte forma:

def binary_search(x, lst, low=None, high=None):

      if low == None : low = 0

    if high == None : high = len(lst)-1

      mid = low + (high - low) // 2

     if low > high :

                 return None

     elif lst[mid] == x :

        return mid

      if lst[mid] > x :

         newlow = low

        newhigh = mid-1

      else:

         newlow = mid+1

         newhigh = high

      return binary_search(x, lst, newlow, newhigh)