Cuidado com funções recursivas!!!

Eis um exemplo e uma pergunta: Se cada chamada à função ack() leva ‘n’ microsegundos, quanto tempo você acha que o programa abaixo leva para ser executado?

#include <stdio.h>

/* A função abaixo é claramente recursiva, mas não é uma recursividade 'infinita'!
   Ela claramente tem uma condição de saida e, em cada chamada recursiva, os valores de
   'm' e/ou 'n' são decrementados! */
int ack(int m, int n)
{
  int ans;

  if (m == 0)
    ans = n + 1;
  else if (n == 0)
    ans = ack(m - 1, 1);
  else
    ans = ack(m - 1, ack(m, n - 1));

  return ans;
}

int main(int argc, char **argv)
{
  int i, j;

  /* Tenta listar apenas os 36 primeiros resultados! Só 36! */
  for (i = 0; i &amp;lt. 6; i++)
    for (j = 0; j &amp;lt. 6; j++)
      printf("ack(%d, %d) = %d\n", i, j, ack(i,j));

  return 0;
}

Se você não encontrar uma resposta facilmente, dê uma olhada em Ackermann function e descubra!

Dica: Nem adianta executar e medir o tempo!

Outra pergunta: Dá para transformar a função recursiva ack() em um simples loop “for”, acabando com a recursividade?

Anúncios

Deixe um comentário

Faça o login usando um destes métodos para comentar:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s