Java - Recursividade

Introdução a recursão: conceito, utilização e exemplos.

Recursividade

Um objeto é dito recursivo se pode ser definido em termos  de si próprio.

Recursividade não é um comando, mas uma "habilidade" de uma função chamar a si mesma. Isto não é privilégio apenas da linguagem C, muitas outras linguagens como Java, Visual Basic, entre outras também é possível ser feito isso.

É importante entender este conceito, pois ele é muito útil e pode ajudar a deixar seu algoritmo muito mais simples.

Em uma função recursiva, a cada chamada é criada na memória uma nova ocorrência da função com comandos e variáveis “isolados” das ocorrências anteriores.

A função é executada até que todas as ocorrências tenham sido resolvidas.

Porém um problema que surge ao usar a recursividade é como fazê-la parar. Caso o programador não tenha cuidado é fácil cair num loop infinito recursivo o qual pode inclusive esgotar a memória

Toda recursão é composta por:

• Um caso base, uma instância do problema que pode ser solucionada facilmente. Por exemplo, é trivial fazer a soma de uma lista com um único elemento.
• Uma ou mais chamadas recursivas, onde o objeto define-se em termos de sí próprio, tentando convergir para o caso base. A soma de uma lista de n elementos pode ser definida a partir da lista da soma de n - 1 elementos.

Exemplo:

#include

#include

int soma(int m, int n) {

   

    if (m == n)

       return n;

    else

        return m + soma(m+1, n);

}

main()

{

 

  int resultado = soma(5,10);

  printf("SOMA RECURSIVA %d \n",resultado);

 

  system("PAUSE");        

  return 0;

}

Pilha de execução:

A cada chamada de função o sistema reserva espaçoo para parâmetros, variáveis locais e valor de retorno.

main	soma(5,10)
soma	retorno = ??? m = 5; n = 10;
soma	retorno= ??? m = 6; n = 10
soma	retorno = ??? m=7; n=10;
soma	retorno = ??? m=8; n=10;
soma	retorno = ??? m=9; n=10;
soma	retorno = ??? m=10; n=10;

Para entender melhor adicionar os prints no programa conforme abaixo:

#include

#include

int soma(int m, int n) {

   

    if (m == n){

       int ret = n;  

       printf("%d == %d = %d \n ",m,n,ret);      

       return ret;

    }  

    else{

        int ret = m + soma(m+1, n);  

        printf("%d + soma(%d+1, %d) = %d \n ",m,m,n,ret);      

        return ret;

    }    

}

main()

{

 

  int resultado = soma(5,10);

  printf("SOMA RECURSIVA %d \n",resultado);

 

  system("PAUSE");        

  return 0;

}

Potência usando recursividade.

[pic 1]

Exemplo:

#include

#include

double pot(double x, int n) {

       if (n == 0)

          return 1;

       else if (n < 0)

...