1. Funções recursivas, em termos leigos, significam que a própria função chama a si mesma...
Tais como: n!=n(n-1)!
Você define a função f(n)=nf(n-1)
E f(n-1) é uma função desta definição. . Isso é recursão
2. Por que usar a recursão: O objetivo da recursão é simplificar o design do programa e torná-lo mais fácil de ler.
3. Desvantagens da recursão: Embora as funções não recursivas sejam altamente eficientes, são difíceis de programar e têm pouca legibilidade. A desvantagem das funções recursivas é que elas aumentam a sobrecarga do sistema. Ou seja, cada vez que são recursivas, a memória da pilha ocupa mais espaço.
4. Condições para recursão: deve haver uma declaração para completar a tarefa e os requisitos para recursão devem ser atendidos (reduzir em vez de divergir)
5. Avanço recursivo:
1. Use recursão para calcular o fatorial de n:
Análise: n!=n*(n-1)*(n-2)...*1
public int dReturn(int n){ if(n==1){ return 1;else{ return n*dReturn(n-1);2. Use a função recursiva para calcular a acumulação de 1 a n: 1+2+3+4+..+n
public int dReturn(int n){ if(n==1){ return 1;else{ return n+dReturn(n-1); 3. É necessário gerar uma sequência: 1,1,2,3,5,8,11... (cada número é a soma dos dois números anteriores e é necessária uma função recursiva)
Use recursão java para representar uma função: F(n)=F(n-1)+F(n-2);F(0)=1;F(1)=1;
Análise: X1=1;
public int F(int n){ if(n==1){ return 1; }else if(n==2){ return 1;else{ return F(n-1)+F(n-2); } }4.Java usa método recursivo para imprimir inversamente cada elemento em uma matriz inteira
public static void printAll(int índice,int[] arr){ System.out.println(arr[index]); [] args){ int[] arr={1,2,3,4,5};5. Solução de programação: Se uma novilha dá à luz uma vaca todos os anos a partir do quarto ano após o nascimento, quantas vacas existem no enésimo ano?
public static int gado(int n){ if(n<=0){ return 0;else if(n<=3){ return 1;else{ return gado(n-1)+gado(n-3) ; } } public static void main(String[] args){ int n=10; System.out.println(n+"Haverá um total de "+gado(n)+"vacas" após o ano });Quais são os conceitos de recursão, recursão linear e recursão de cauda?
Chamando funções recursivas em Java – encontrando o fatorial de um número
Overflow não é considerado: geralmente apenas o fatorial de 69 pode ser calculado...
Nota: o fatorial de 0 é 0! =1
A representação fatorial de qualquer número natural n maior que 1:
n!=1×2×3×……×n
Ou n!=n×(n-1)!
Procurar o fatorial de 0 abrirá uma calculadora online, que é muito útil! !
teste de pacote;importar java.util.Scanner;classe pública DiGui {public static void main(String[] args) {// TODO Método gerado automaticamente stubSystem.out.println("Insira um número inteiro:");Scanner scan = new Scanner(System.in);int x = scan.nextInt();int resultado = digui(x);System.out.println(result);}//Função recursiva public static int digui(int x){if(x<=0){return 1;}else{return x*digui(x-1 );}}}Recursão: Um processo ou função possui um método para se chamar direta ou indiretamente em sua definição ou descrição. Geralmente transforma um problema grande e complexo em um problema menor semelhante ao problema original a ser resolvido. Este caso ilustra claramente como a recursão pode transformar um problema complexo em um problema menor para resolver. A seguir está um pequeno exemplo para ilustrar o princípio da recursão.
/*** @fileName Test.java* @description ??????????* @date 2012-11-25* @time 17:30* @author wst*/public class Test { static intmultiplicar( int n) { int fatorial; // ?? if ((n == 1) || (n == 0)) { fatorial = n } else { fatorial = n * multiplicar(n - 1); ; } public static void main(String[] args) { System.out.println(multiply(5)); Quando uma função é chamada, é criado espaço para suas variáveis na pilha de tempo de execução. As variáveis da função chamada anteriormente permanecem na pilha, mas são obscurecidas pelas variáveis da nova função e, portanto, não podem ser acessadas.
A função no programa possui duas variáveis: parâmetro n e variável local fatorial. Os diagramas a seguir mostram o estado da pilha, com as variáveis atualmente acessíveis no topo. Todas as outras variáveis chamadas ficam sombreadas em cinza para indicar que não podem ser acessadas pela função atualmente em execução.
Suponha que chamamos a função recursiva com o valor 5. O conteúdo da pilha é o seguinte, com o topo da pilha na parte inferior:
n multiplicar(n) fatorial 5 multiplicar(5) 5*multiplicar(4) //Primeira chamada 4 multiplicar(4) 4*multiplicar(3) //Segunda chamada 3 multiplicar(3) 3*multiplicar(2 ) //O terceira chamada 2 multiplicar(2) 2*multiply(1) //A quarta chamada 1 multiplicar(1) 1 //A quinta chamada
A partir das informações acima, pode-se ver facilmente como a recursão minimiza gradativamente um problema para resolvê-lo. A partir da chamada do método, os resultados fatoriais serão colocados na pilha até que a chamada do método termine e, finalmente, os resultados são retornados um por um. do topo da pilha. Após a substituição uma por uma, o resultado é o seguinte:
n=1 1 retorna 1 para cima
n=2 2*multiply(1) retorna 2*1=2 para cima
n=3 3*multiply(2) retorna 3*(2*1)=6 para cima
n=4 4*multiply(3) retorna 4*(3*(2*1))=24 para cima
n=5 5*multiply(4) retorna para cima 5*(4*(3*(2*1)))=120
Nota: Porque multiplicar(1) ou multiplicar(0) retorna um valor de 1
Portanto, há 2*multiplicar(1)=2*1=2
E como multiplicar(2) atende à condição de recursão, ele pode ser transformado em 2*multiply(1) após a recursão.
Portanto, há 3*multiplicar(2)=3*(2*multiplicar(1))=3*(2*1)=6
Porque multiplicar(3) pode ser reduzido para 3*multiplicar(2) após recursão
Então multiplique(4)=4*multiplique(3)=4*(3*multiplique(2))=4*(3*(2*1))=24
Por analogia, multiplique(5)=5*multiplique(4)
Pode ser reduzido para 5*(4*multiplicar(3))=5*(4*3*(multiplicar(2)))=5*(4*(3*(2*1)))=120
Vamos dar uma olhada nas informações do bytecode:
public class Test estende java.lang.Object{ public Test() Código: 0: aload_0 1: invocaespecial #1; //Método java/lang/Object."<init>":()V 4: return static intmultiplicação (int); Código: 0: iload_0 1: iconst_1 //Empurra a constante de tipo int 1 na pilha 2: if_icmpeq 9 //Compare dois valores do tipo int. Se eles forem iguais, pule para a posição 9. Esta é a função de curto-circuito de ||5: iload_0 //Isso é executado quando a primeira condição não é válida, começando pela variável local 0 Load. um valor do tipo int (coloque o valor de n na pilha) 6: ifne 14 //Compare, se não for igual a 0, salte para a posição 14. Nota: Como o padrão aqui é comparado com 0, não há necessidade de alterar a constante para 0 Push 9: iload_0 //Se não houver salto em ifne, carregue o valor do tipo int da variável local 0 (coloque o valor de n na pilha) 10: istore_1 //Armazene o valor do tipo int na variável local 1 (coloque o valor no topo da pilha) Ou seja, o valor da variável local 0 é colocado na pilha e então armazenado na variável local 1) 11: goto 23 //Pula incondicionalmente para a posição 23 14: iload_0 //Comparação na posição 6, se não for igual a 0, execute esta instrução e carregue o valor do tipo int da variável local 0 (coloque o valor de n na pilha) 15: iload_0 //Carregue o valor do tipo int do local variável 0 (empurre o valor de n para a pilha) Empurre o valor de n para a pilha) 16: iconst_1 //Empurre a constante do tipo int 1 para a pilha, a constante 1 é 1 de n-1 no código 17: isub //Executa a operação de subtração, n-1 18: invocastatic #2; multiplicar:(I)I, chamar método multiplicar 21: imul //Executar operação de multiplicação, n * multiplicar(n - 1) 22: istore_1 //Armazenar valor do tipo int na variável local 1, fatorial=... 23: iload_1 / /Carrega o valor do tipo int da variável local 1 (coloca o resultado do fatorial na pilha) 24: ireturn //O método retorna public static void main(java.lang.String[]); #3; //Campo java/lang/System.out:Ljava/io/PrintStream; 3: iconst_5 4: invocaestático #2; //Método multiplique:(I)I 7: invocavirtual #4; /PrintStream.println:(I)V 10: retornar }