Função Recursiva - java.lang.StackOverflowError

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).

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;
        
    }
    
}

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