Função Recursiva - java.lang.StackOverflowError

Programação Java
#1

Estou fazendo uns trabalhos pra faculdade testando algumas funções recursivas e iterativas, segue a função que criei:

public static void buscaRecursiva(ArrayList<Integer> num, int tamanho, int numero){
			if(num.get(tamanho)==numero){
				iguaisRecursivo = iguaisRecursivo+1;
			}
			if(tamanho > 0){
				buscaRecursiva(num, tamanho -1, numero);
			}
			else{
				System.out.println("O numero "+ numero +" aparece "+iguaisRecursivo+" vez(es) na busca recursiva!!");
			}
		}

como podem ver, ela busca em um Array List e imprime na tela se e quantas vezes o numero fornecido pelo usuário é encontrado,
no entanto, quando passo um Array muito grande(100.000 elementos por exemplo) ele me retorna o seguinte erro :

[color=red]“Exception in thread “main” java.lang.StackOverflowError
at br.funcesi.PAA.Principal.buscaRecursiva(Principal.java:33)
at br.funcesi.PAA.Principal.buscaRecursiva(Principal.java:37)
at br.funcesi.PAA.Principal.buscaRecursiva(Principal.java:37)
at br.funcesi.PAA.Principal.buscaRecursiva(Principal.java:37)
at br.funcesi.PAA.Principal.buscaRecursiva(Principal.java:37)”[/color]

entretanto, quando passo um de 1.000 elementos ele funfa de boassa…e quando faço o mesmo tipo de pesquisa com uma função iterativa
também rola de boa!! Alguém sabe me dizer o que está causando esse erro?? Acho que pode ser algo relacionado com memória…será que é??

#2

O próprio erro já diz. StackOverflow => Estouro da pilha.
Imagine só um método ser empilhado 100k vezes! A quantidade de memória necessária para seu algoritmo executar é linear, sendo assim, além do próprio empilhamento dos métodos, há a sobrecarga da declaração das variáveis. Nunca você irá usar um algoritmo recursivo que tem crescimento linear, pois pode acontecer justamente este problema ai. Espero que o seu professor tenha pedido este tipo de exercício justamente para você detectar este problema. O seu algoritmo é uma busca sequencial. Agora, se fosse uma busca binária recursiva, o problema seria muito menor (muito mesmo, continue lendo abaixo), visto que tanto o crescimento em tempo quanto o crescimento em memória seria logarítmico (em base 2), visto que a cada recursão seu problema é dividido por dois.

Uma coisa que achei muito estranha é você usar uma lista ao invés de um array simples… Um exemplo de uma busca recursiva e que não estoura a pilha para valores EXTREMAMENTE altos é dado por algo como o código abaixo (algoritmo clássico de busca binária).

[code]public class Foo{

public static void main( String[] args ) {
    System.out.println( buscaBinaria( new int[]{ 1, 3, 5, 7, 9 }, 9 ) );
}

public static boolean buscaBinaria( int[] dados, int valor ) {
    return buscaBinariaRecursiva( dados, valor, 0, dados.length - 1 );
}

private static boolean buscaBinariaRecursiva( 
        int[] dados, int valor, int ini, int fim ) {
    
    int meio = ( ini + fim ) / 2;
    
    if ( ini <= meio ) {
        if ( valor == dados[meio] ) {
            return true;
        } else if ( valor < dados[meio] ) {
            return buscaBinariaRecursiva( dados, valor, ini, meio - 1 );
        } else {
            return buscaBinariaRecursiva( dados, valor, meio + 1, fim );
        }
    }
    
    return false;
    
}

}[/code]

O método buscaBinaria utilizará o buscaBinariaRecursiva para fazer a busca e retornará true caso o valor seja encontrado ou false caso contrário. Em anexo envio um gráfico mostrando duas funções, sendo que uma tem crescimento linear (sua busca recursiva, em vermelho) e outra tem crescimento logarítmico (a que postei, em verde). Note que para uma entrada de 1000000000000000 (10 elevado a 14), sua função teria a mesma quantidade de empilhamentos, enquanto a minha teria menos que 100. O gráfico está em escala logarítmica para nós podermos ver o comportamento das funções em intervalos grandes. O eixo x representa a quantidade de itens da entrada e o eixo y o tempo gasto ou a quantidade de memória (sem considerar cache, etc.). Outro ponto que esqueci de falar acima é que a busca binária só funciona se o seu array estiver ordenado. Você deve ter percebido isso ao entender o algoritmo.

[]'s

#3