I aí galera do fórum, tudo bem aí com todo mundo?!
Minha dúvida é uma dúvida básica e rápida. Gostaria de saber, porque eu já ouvi falar que sim, se recursividade em Java tem um limite de “profundidade”, vamos dizer assim.
Gostaria de saber se eu posso chamá-la infinitamente. E se realmente tem limite, qual é aproximadamente a quantidade máxima de chamadas?!
E o comentário do cara foi:
"O limite relativamente baixo no tamanho do array, deve-se ao facto de a função de criação do array ser recursiva, e rapidamente se exceder o limite de recursividade do Java. "
Porem não sei qual é esse limite, fazendo um teste na JVM da Sun com a configuração default, a exceção foi lançada apos 16685 chamadas, mas acredito que isso possa variar de acordo com a implementação da JVM ou da configuração, vale dar uma olhada na especificação pra ver se tem algo a respeito.
jairelton
Muito obrigado pela ajuda e pela informação cara.
Perguntei isso porque recursividade é uma coisa bem interessante de utilizar, um pouco mais complexa e resolve, as vezes, muitos casos. Mas o fato é que eu já ouvi alguns recomendações contra mesmo, devido a quantidade do uso de memória e o possível estouro de pilha da memória.
Aproveitando que vc tocou no assunto, eu ouvi falar que o compilador java faz uma otimização de código e que algumas vezes transforma o código recursivo em um iterativo que realiza o mesmo trabalho mas consome menos recursos. Alquem sabe algo a respeito?
Oi, para completar, sim, todo problema que você resolve usando recursão, você pode programar usando iteração, alias, use sempre iteração se souber como fazer.
A recursão é ruim, porque é preciso guardar o ‘estado’ do método antes da chamada recursiva para ai poder continuar o processamento depois, e ai quando acaba esse espaço, ocorre o stack overflow.
Existe uma forma de programar com recursividade que possibilita o compilador dar uma ‘melhorada’ (se tiver essa funcionalidade), que é usar recursão de cauda, você constroi o método recursivo processa o que tem que processar e depois faz a chamada recursiva, desta forma, o compilador poder perceber que você não vai mais usar as variaveis (que formam o ‘estado’) e não grava elas na pilha.
Só um adendo… nem todo problema que pode ser resolvido utilizando recursão pode ser resolvido utilizando iteração. Se isso fosse possível, seria o fim da maioria dos algoritmos de criptografia…
Os algoritmos mais pesados, como o famoooooso Caixeiro Viajante, estão na categoria de problemas NP completos, que (ainda) só possuem solução não-polinomial (ou seja, bota usar recursividade).
Depois é legal dar uma lida nessa história de problemas polinomiais, não-polinomiais e não-polinomiais completos, a base pruma boa análise de algoritmos
Em tempo: quando eu disse ali que o problema não poderia ser resolvido, leia-se “ainda”. Tem uma fundação que promete dar 1 milhao de dolares pro nerd que conseguir resolver um problema NP completo em tempo polinomial (ou seja, sem usar recursividade).
O CV naum tem solucao perfeita, problemas NP completos naum tem solucao perfeita, poder levar a eternidade para achar a solucao eh o mesmo que dizer que naum tem solucao.
Outra coisa, o CV pode ser “resolvido” usando busca em arvores, primeiro noh gera visinhos, vc analisa visinhos que geram novos visinhos e assim por diante, tambem ateh a eternidade, mas enfim, eh possivel implementar isso sem usar recursividade.
Iteracao naum quer dizer: “tempo aceitavel” e qualquer coisa resolvida por ela eh considerado problemas P, e ser NP completo naum quer dizer que o problema pode ser resolvido com uma puta recursao e sim que o problema cresce de tal forma que o numero de iteracoes ou recursoes (chega a ser redundante falar “iteracoes ou recursoes”) que o algoritmo tera de fazer para achar a solucao aumente de forma exponencial
Ué, muitos dos problemas resolvidos atualmente levariam a eternidade se executados nos primeiros computadores.[/quote]
Mas nenhum desses problemas era um NP completo :razz:
Aqueles problemas naum podiam ser resolvidos por limitacao de hardware, e as pessoas ja sabiam disso, entao era soh uma questao de tempo para o hardware evoluir e os problemas serem resolvidos.
Os NP completos naum possuem solucao em tempo polinomial, entao mesmo o computador mais rapido do mundo, ou daqui a 1000 anos de evolucao de hardware, se ninguem achar uma forma (algoritmo) de resolver ele em tempo polinomial, ainda vai levar a eternidade para achar a resposta para qualquer entrada. O processamento do hardware pode aumentar, mas mesmo assim vai existir um valor que ira levar o tempo de processamento eternidade, isso devido ao problema, eh por isso que esse naum saum problemas que serao resolvidos com o avanco do hardware como aqueles, e eh por isso que eles naum tem solucao (perfeita).
E ai se naum me engano, caso algum dia alguem prove que um problema NP completo pode ser resolvido em termpo polinomial (ou seja, o problema entraria na classe de problemas P), entao provaria que todos outros NP completos poderiam ser resolvidos em tempo P… seria um dos maiores avacandos da computacao. Hoje para resolver esse tipo de problemas saum usados tecnicas de IA como algoritmos geneticos ou aplicacao de heuristicas, mas essas solucoes naum daum a resposta perfeita, apenas “uma resposta muito boa” para os problema.
Eu soh estou falando que esses problemas naum tem por caracteristica serem recursivos, eles tem caracteristicas de que a solucao perfeita deles eh dada por um algoritmo onde o tempo de execucao cresce de forma exponencial, e esse aumento, nem todos computadores do mundo daum conta de computar para qualquer entrada.
