O que é recursão?

https://stackoverflow.com/questions/33923

09-06-2019
|

Pergunta

Enquanto começando a aprender lisp, eu me deparei com o termo recursiva.O que isso significa exatamente?

Solução

Considere uma função simples que adiciona N primeiros números inteiros.(e.g. sum(5) = 1 + 2 + 3 + 4 + 5 = 15).

Aqui é um simples JavaScript implementação que usa recursão:

function recsum(x) {
    if (x===1) {
        return x;
    } else {
        return x + recsum(x-1);
    }
}

Se você chamou recsum(5), isso é o que o interpretador JavaScript avaliar:

recsum(5)
5 + recsum(4)
5 + (4 + recsum(3))
5 + (4 + (3 + recsum(2)))
5 + (4 + (3 + (2 + recsum(1))))
5 + (4 + (3 + (2 + 1)))
15

Observe como cada chamada recursiva tem de ser concluída antes que o interpretador JavaScript começa a realmente fazer o trabalho de calcular a soma.

Aqui está um rabo-versão recursiva da mesma função:

function tailrecsum(x, running_total=0) {
    if (x===0) {
        return running_total;
    } else {
        return tailrecsum(x-1, running_total+x);
    }
}

Veja a sequência de eventos que poderiam ocorrer se você chamou tailrecsum(5), (o que seria efetivamente ser tailrecsum(5, 0), porque o padrão segundo argumento).

tailrecsum(5, 0)
tailrecsum(4, 5)
tailrecsum(3, 9)
tailrecsum(2, 12)
tailrecsum(1, 14)
tailrecsum(0, 15)
15

Na recursiva caso, com avaliação da chamada recursiva, o running_total é atualizado.

Nota:O original de resposta usados exemplos a partir do Python.Estes foram alteradas para JavaScript, desde modernos JavaScript intérpretes de apoio chamada de cauda de otimização mas Python intérpretes não.

Outras dicas

No tradicional recursão, o modelo típico é que você realizar suas chamadas recursivas primeiro e, em seguida, tomar o valor de retorno da chamada recursiva e calcular o resultado.Desta forma, você não obter o resultado do cálculo até que você tenha retornado de cada chamada recursiva.

No recursão, você executar os cálculos primeiro e, em seguida, você executar a chamada recursiva, passando os resultados dos seus atuais passo para o próximo passo recursivo.Isso resulta na última declaração sendo em forma de (return (recursive-function params)). Basicamente, o valor de retorno de qualquer dado recursiva passo é o mesmo que o valor de retorno da seguinte chamada recursiva.

A conseqüência disso é que uma vez que você está pronto para executar o próximo passo recursivo, você não precisa de pilha atual quadro mais.Isso permite que para alguns de otimização.Na verdade, com um escrito corretamente compilador, você nunca deve ter um estouro de pilha snicker com uma cauda chamada recursiva.Simplesmente reutilizar o atual quadro de pilha para o próximo passo recursivo.Eu tenho certeza de Lisp faz isso.

Um ponto importante é que com recursão é essencialmente equivalente ao loop.Não é apenas uma questão de otimização do compilador, mas um fato fundamental sobre a expressividade.Isto vai ambas as maneiras:você pode tomar qualquer loop do formulário

while(E) { S }; return Q

onde E e Q são expressões e S é uma sequência de instruções, e transformá-lo em um rabo de função recursiva

f() = if E then { S; return f() } else { return Q }

Claro, E, S, e Q tem de ser definida para calcular a algumas de valor interessante sobre algumas variáveis.Por exemplo, a função de loop

sum(n) {
  int i = 1, k = 0;
  while( i <= n ) {
    k += i;
    ++i;
  }
  return k;
}

é equivalente ao recursiva da função(s)

sum_aux(n,i,k) {
  if( i <= n ) {
    return sum_aux(n,i+1,k+i);
  } else {
    return k;
  }
}

sum(n) {
  return sum_aux(n,1,0);
}

(Esta "quebra" da cauda-função recursiva com uma função com menos parâmetros é um funcional comum de expressão.)

Este trecho do livro Programação em Lua mostra como fazer um bom recursão (na Lua, mas deve aplicar-se a Lisp também) e por que é melhor.

Um chamada de cauda [recursão] é um tipo de vestido goto como uma chamada.Uma chamada de cauda acontece quando um chamadas de função de outro, como seu último a ação, portanto, ele não tem mais nada a fazer.Por exemplo, no código a seguir, a chamada para g é uma chamada de cauda:
function f (x)
  return g(x)
end
Depois de f chamadas g, ele não tem mais nada para o fazer.Em tais situações, o programa de não precisa voltar para a chamada função quando a função chamada termina.Portanto, após a chamada de cauda, o programa não precisa manter qualquer informações sobre a função de chamada na pilha....

Porque um bom chamada de cauda que não utiliza o espaço de pilha, não há limite no número de "aninhadas" cauda chama que um o programa pode fazer.Podemos, por exemplo, chamar a seguinte função com qualquer número como argumento;ele nunca vai estouro de pilha:
function foo (n)
  if n > 0 then return foo(n - 1) end
end
...Como eu disse anteriormente, uma chamada de cauda é uma tipo de goto.Como tal, um bem útil aplicação do próprio rabo chamadas em A Lua é para a programação de máquinas de estado.Tais aplicações podem representar cada estado, por meio de uma função;para alterar o estado é ir para (ou chamada) a função.Como um exemplo, vamos considere um simples jogo de labirinto.O labirinto possui vários quartos, cada um com até quatro portas:norte, sul, leste, e oeste.Em cada etapa, o usuário entra em um direção de movimento.Se há uma porta nessa direção, o usuário vai para o quarto correspondente;caso contrário, o programa imprime um aviso.O objetivo é para ir do início de um quarto a um final o quarto.

Este jogo é uma típica máquina de estado, onde a sala atual é o estado.Podemos implementar tal labirinto com um função para cada quarto.Nós usamos cauda chamadas para passar de uma sala para outro.Um pequeno labirinto com quatro quartos poderia ter esta aparência:
function room1 ()
  local move = io.read()
  if move == "south" then return room3()
  elseif move == "east" then return room2()
  else print("invalid move")
       return room1()   -- stay in the same room
  end
end

function room2 ()
  local move = io.read()
  if move == "south" then return room4()
  elseif move == "west" then return room1()
  else print("invalid move")
       return room2()
  end
end

function room3 ()
  local move = io.read()
  if move == "north" then return room1()
  elseif move == "east" then return room4()
  else print("invalid move")
       return room3()
  end
end

function room4 ()
  print("congratulations!")
end

Então você vê, quando você faz uma chamada recursiva como:

function x(n)
  if n==0 then return 0
  n= n-2
  return x(n) + 1
end

Esta não é a cauda recursiva porque você ainda tem coisas para fazer (suplemento 1) em que a função após a chamada recursiva é feita.Se você introduzir um número muito elevado provavelmente vai causar um estouro de pilha.

Regulares usando recursão, a cada chamada recursiva empurra outra entrada para a pilha de chamadas.Quando a recursividade é concluída, em seguida, o aplicativo tem a pop cada entrada off todo o caminho de volta para baixo.

Com recursão, dependendo do idioma, o compilador pode ser capaz de recolher a pilha para baixo para uma entrada, assim você economiza espaço na pilha...Uma grande consulta recursiva pode realmente causar um estouro de pilha.

Basicamente Cauda recursions são capazes de ser otimizado para a iteração.

Em vez de explicar com palavras, aqui está um exemplo.Este é um Esquema de versão da função fatorial:

(define (factorial x)
  (if (= x 0) 1
      (* x (factorial (- x 1)))))

Aqui está uma versão do fatorial que é recursiva:

(define factorial
  (letrec ((fact (lambda (x accum)
                   (if (= x 0) accum
                       (fact (- x 1) (* accum x))))))
    (lambda (x)
      (fact x 1))))

Você vai notar na primeira versão que a chamada recursiva a verdade é alimentado para a multiplicação de expressão, e, portanto, o estado tem de ser guardado na pilha ao fazer a chamada recursiva.Na recursiva versão, não há nenhum outro S-expressão de espera para o valor da chamada recursiva, e uma vez que não há mais trabalho a fazer, o estado não tem de ser guardado na pilha.Como regra geral, o Esquema de cauda-funções recursivas uso constante de espaço de pilha.

O jargão arquivo tem a dizer sobre a definição de recursão:

recursão /n./

Se você não está doente já, ver recursão.

Recursão refere-se à chamada recursiva sendo o último na última instrução de lógica na recursiva do algoritmo.

Normalmente, na recursão, você tem um base-caso que é o que deixa as chamadas recursivas e começa a estalar a pilha de chamadas.Para usar um exemplo clássico, embora mais C-ish de Lisp, a função factorial ilustra com recursão.A chamada recursiva ocorre depois de verificar a base de caso a condição.

factorial(x, fac=1) {
  if (x == 1)
     return fac;
   else
     return factorial(x-1, x*fac);
}

A chamada inicial para factorial seria factorial(n) onde fac=1 (valor padrão) e n é o número para o qual o factorial é para ser calculado.

Isso significa que em vez de precisar de empurrar o ponteiro de instrução na pilha, você pode simplesmente saltar para o topo de uma função recursiva e continuar a execução.Isso permite funções para recurse indefinidamente sem transbordar a pilha.

Eu escrevi uma blog post sobre o assunto, que tem gráfica exemplos do que os quadros de pilha semelhante.

Aqui está um rápido trecho de código a comparação de duas funções.A primeira é tradicional recursão para encontrar o fatorial de um número dado.O segundo usa recursão.

Muito simples e intuitiva de entender.

Uma maneira fácil de saber se uma função recursiva é uma cauda recursiva é se ela retorna um valor concreto no caso base.O que significa que ele não retorna 1 ou true ou qualquer coisa assim.Ele será mais do que provável que retornar alguma variação de um dos parâmetros do método.

Uma outra maneira de dizer é se a chamada recursiva é livre de qualquer adição, aritmética, modificação, etc...O que significa nada, mas um puro chamada recursiva.

public static int factorial(int mynumber) {
    if (mynumber == 1) {
        return 1;
    } else {            
        return mynumber * factorial(--mynumber);
    }
}

public static int tail_factorial(int mynumber, int sofar) {
    if (mynumber == 1) {
        return sofar;
    } else {
        return tail_factorial(--mynumber, sofar * mynumber);
    }
}

A melhor maneira de entender para mim tail call recursion é um caso especial de recursividade, onde o última chamada(ou a chamada de cauda) é a função em si.

Comparando os exemplos fornecidos em Python:

def recsum(x):
 if x == 1:
  return x
 else:
  return x + recsum(x - 1)

^RECURSÃO

def tailrecsum(x, running_total=0):
  if x == 0:
    return running_total
  else:
    return tailrecsum(x - 1, running_total + x)

^RECURSÃO

Como você pode ver na versão recursiva geral, a chamada final do bloco de código é x + recsum(x - 1).Então, depois de chamar o recsum método, não há outra operação que é x + ...

No entanto, na cauda recursiva versão, a chamada final(ou a chamada de cauda) no bloco de código é tailrecsum(x - 1, running_total + x) o que significa que a última chamada é feita para o método em si e nenhuma operação.

Este ponto é importante porque recursão, como visto, aqui, não é fazer a memória crescer porque quando subjacentes VM vê uma função chamar a si própria em um rabo de posição (a última expressão a ser avaliada em uma função), ele elimina o atual quadro de pilha, que é conhecido como Tail Call Optimization(TCO).

EDITAR

NB.Tenha em mente que o exemplo acima é escrito em Python, cujo tempo de execução não suporta o custo total de propriedade.Este é apenas um exemplo para explicar o ponto.O TCO é suportado em línguas como o Scheme, Haskell etc

Em Java, aqui está uma possível cauda implementação recursiva de Fibonacci função:

public int tailRecursive(final int n) {
    if (n <= 2)
        return 1;
    return tailRecursiveAux(n, 1, 1);
}

private int tailRecursiveAux(int n, int iter, int acc) {
    if (iter == n)
        return acc;
    return tailRecursiveAux(n, ++iter, acc + iter);
}

Contraste isso com o padrão de implementação recursiva:

public int recursive(final int n) {
    if (n <= 2)
        return 1;
    return recursive(n - 1) + recursive(n - 2);
}

Aqui é um Common Lisp exemplo que faz fatoriais usando rabo-de recursão.Devido à pilha-menos a natureza, poderia realizar insanamente grande factorial cálculos ...

(defun ! (n &optional (product 1))
    (if (zerop n) product
        (! (1- n) (* product n))))

E, em seguida, para a diversão que você pode tentar (format nil "~R" (! 25))

Eu não sou um programador Lisp, mas eu acho que este vai ajudar.

Basicamente, é um estilo de programação, tais que a chamada recursiva é a última coisa que você faz.

Em suma, uma recursão tem a chamada recursiva como o última instrução na função de modo que ela não tem que esperar para a chamada recursiva.

Portanto, esta é uma recursão i.e.N(x - 1, p * x) é a última instrução na função onde o compilador é inteligente para perceber que ela pode ser optimizada para um ciclo (fatorial).O segundo parâmetro p realiza o intermédio de valor do produto.

function N(x, p) {
   return x == 1 ? p : N(x - 1, p * x);
}

Este é o não-recursiva jeito de escrever acima factorial (embora alguns compiladores de C++ pode ser capaz de optimizar-lo de qualquer maneira).

function N(x) {
   return x == 1 ? 1 : x * N(x - 1);
}

mas este não é:

function F(x) {
  if (x == 1) return 0;
  if (x == 2) return 1;
  return F(x - 1) + F(x - 2);
}

Eu escrevi um longo post intitulado "Entender Recursão – Visual Studio C++ – Vista De Montagem"

aqui está um Perl 5 versão do tailrecsum função mencionada anteriormente.

sub tail_rec_sum($;$){
  my( $x,$running_total ) = (@_,0);

  return $running_total unless $x;

  @_ = ($x-1,$running_total+$x);
  goto &tail_rec_sum; # throw away current stack frame
}

Este é um trecho do Estrutura e Interpretação de Programas de Computador sobre recursão de cauda.

Em contraste iteração e recursão, devemos ter o cuidado de não confundir a noção de um processo recursivo com a noção de uma procedimento recursiva.Quando descrevemos um procedimento recursivo, estamos referindo-se ao sintática fato de que a definição de procedimento refere-se (diretamente ou indiretamente) para o procedimento em si.Mas quando nós descrever um processo de como seguir um padrão que é, digamos, linearmente recursiva, estamos falando sobre como o processo evolui, não sobre a sintaxe de como um procedimento escrito.Pode parecer perturbadora que nós nos referimos a um procedimento recursiva como fato-iter como gerar uma processo iterativo.No entanto, o processo realmente é iterativo:Seu estado é capturado completamente pelos seus três variáveis de estado, e um intérprete precisa manter o controle de apenas três variáveis, a fim de executar o processo.

Uma razão, que a distinção entre processo e procedimento pode ser confuso é que a maioria das implementações de linguagens comuns (incluindo Ada, Pascal, e C) são projetados de tal forma que a interpretação de qualquer recursiva procedimento consome uma quantidade de memória que aumenta com o número de chamadas de procedimento, mesmo quando o processo descrito é, em princípio, iterativo.Como consequência, essas línguas podem descrever iterativo processos, apenas recorrendo a finalidade especial de "construções de loop" como fazer, repetir, até que, e quando. A implementação de Regime de não compartilhar esse defeito.Ele irá executar um processo iterativo em constante espaço, mesmo se o processo iterativo é descrito por um procedimento recursiva.Um implementação com esta propriedade é chamada recursiva. Com um recursiva implementação, iteração pode ser expresso usando a procedimento ordinário mecanismo de chamada, de modo que especial iteração construções são úteis apenas como um açúcar sintático.

Recursão é a vida que você está vivendo agora.Você constantemente a reciclar o mesmo quadro de pilha, mais e mais, porque não há nenhuma razão ou meios para regressar a um "antigo" quadro.O passado é longo e feito com tanto pode ser descartado.Você obter um quadro, sempre em movimento para o futuro, até que seu processo inevitavelmente morre.

_{A analogia ao considerar alguns processos podem utilizar quadros adicionais, mas ainda são considerados recursiva se a pilha não crescer infinitamente.}

A recursão é uma função recursiva, onde as chamadas de função se no final ("cauda") da função em que nenhum cálculo é feito após o retorno da chamada recursiva.Muitos compiladores de otimizar a alterar uma chamada recursiva para um rabo recursivo ou iterativo chamada.

Considere o problema de calcular factorial de um número.

Uma abordagem simples poderia ser:

  factorial(n):

    if n==0 then 1

    else n*factorial(n-1)

Suponha que você chamar factorial(4).A árvore de recursão seria:

       factorial(4)
       /        \
      4      factorial(3)
     /             \
    3          factorial(2)
   /                  \
  2                factorial(1)
 /                       \
1                       factorial(0)
                            \
                             1

A máxima profundidade de recursão no caso acima é O(n).

No entanto, considere o seguinte exemplo:

factAux(m,n):
if n==0  then m;
else     factAux(m*n,n-1);

factTail(n):
   return factAux(1,n);

Árvore de recursão para factTail(4) seria:

factTail(4)
   |
factAux(1,4)
   |
factAux(4,3)
   |
factAux(12,2)
   |
factAux(24,1)
   |
factAux(24,0)
   |
  24

Aqui também, o máximo de profundidade de recursão é O(n), mas nenhuma das chamadas adiciona variável para a pilha.Portanto, o compilador pode acabar com uma pilha.

Para compreender algumas das principais diferenças entre a cauda-chamada de recursão e não-cauda-chamada de recursão podemos explorar o .NET a implementação dessas técnicas.

Aqui está um artigo com alguns exemplos em C#, F# e C++\CLI: Aventuras na Recursão em C#, F# e C++\CLI.

C# não otimizar o rabo-chamada de recursão enquanto F# faz.

As diferenças de princípio envolvem ciclos vs.Cálculo Lambda.C# é projetado com loops em mente enquanto F# é construído a partir de princípios do cálculo Lambda.Por muito bom (e livre), livro sobre os princípios do cálculo Lambda, consulte Estrutura e Interpretação de Programas de Computador, por Abelson, Sussman, e Sussman.

Em relação cauda chamadas em F#, por muito bom artigo introdutório, consulte Introdução detalhada à Cauda Chamadas em F#.Finalmente, aqui está um artigo que cobre a diferença entre o não-recursão e rabo-chamada de recursão (F#): Cauda-a recursividade vs.não recursão em fá sustenido.

Se você quiser ler sobre algumas das diferenças de design de cauda chamada de recursividade entre C# e F# veja A geração de Cauda Chamada de Código em C# e F#.

Se você se importa o suficiente para querer saber o que as condições de impedir que o compilador C# a partir da realização de cauda chamada otimizações, consulte este artigo: JIT do CLR cauda-chamada condições.

Existem dois tipos básicos de recursões: cabeça de recursão e recursão.

No cabeça de recursão, uma função faz a sua chamada recursiva e, em seguida, realiza alguns cálculos mais, talvez usando o resultado do chamada recursiva, por exemplo.

Em um cauda recursiva de função, todos os cálculos acontecer primeiro e a chamada recursiva é a última coisa que acontece.

Tomadas de este super legal o post.Por favor, considere a possibilidade de lê-lo.

A recursividade, uma função chamar a si própria.Por exemplo:

(define (un-ended name)
  (un-ended 'me)
  (print "How can I get here?"))

Cauda-a Recursividade significa que a recursividade que concluem a função:

(define (un-ended name)
  (print "hello")
  (un-ended 'me))

Veja, a última coisa onu-terminou função (procedimento, em Regime de jargão) faz é chamar a si.Outra (mais útil) exemplo é:

(define (map lst op)
  (define (helper done left)
    (if (nil? left)
        done
        (helper (cons (op (car left))
                      done)
                (cdr left))))
  (reverse (helper '() lst)))

No gestor de procedimento, a ÚLTIMA coisa que ele faz, se a esquerda não é nulo, é para chamar a si (APÓS os contras de algo e cdr algo).Este é, basicamente, como você mapear uma lista.

O rabo-de recursão tem uma grande vantagem que o interpretador (ou compilador, dependentes do idioma e fornecedor) pode otimizá-lo, e transformá-lo em algo equivalente a um loop while.Como matéria de facto, em Regime de tradição, a maioria dos "for" e "while" loop é feito em um rabo-de recursão forma (não há e enquanto, até onde eu sei).

Esta questão tem um monte de grandes respostas...mas eu não posso ajudar, mas afirmar-se como uma alternativa de assumir como definir o que é "recursão", ou pelo menos "bom recursão." A saber:deve vê-la como uma propriedade de um particular expressão em um programa?Ou será que se deve olhar para ele como uma propriedade de um a implementação de uma linguagem de programação?

Para saber mais sobre o último ponto de vista, não é um clássico papel por Clinger, "Adequada Recursão e a Eficiência do Espaço" (PLDI 1998), que definiu como "adequada recursão" como uma propriedade de uma linguagem de programação de implementação.A definição é construída para permitir a ignorar detalhes de implementação (como se a pilha de chamada, na verdade, é representado através da pilha de tempo de execução ou através de uma pilha atribuídos vinculada lista de quadros).

Para realizar isso, ele utiliza análise assintótica:não de tempo de execução de programas como geralmente se vê, mas, ao invés de programa utilização de espaço.Desta forma, o uso do espaço de uma pilha atribuídos lista ligada vs um tempo de execução de pilha de chamada, acaba por ser assintoticamente equivalente;assim, faz-se a ignorar que a linguagem de programação detalhe de implementação (um detalhe que certamente a matéria um pouco em prática, mas pode lamacentas águas um pouco quando se tenta determinar se uma dada aplicação é satisfazer o requisito de ser "propriedade cauda recursiva")

O papel a pena um estudo cuidadoso para um número de razões:

Ele dá uma definição indutiva de cauda expressões e cauda chamadas de um programa.(Tal definição, e por tais chamadas são importantes, parece ser o assunto da maioria das outras respostas dadas aqui.)

Aqui estão as definições, apenas para fornecer um sabor do texto:
Definição 1 O cauda expressões de um programa escrito no Núcleo do sistema são definidos indutivamente como se segue.
1. O corpo de uma expressão lambda é uma expressão com a cauda
2. Se (if E0 E1 E2) é uma expressão com a cauda, em seguida, ambos E1 e E2 são de cauda de expressões.
3. Nada mais é que uma expressão com a cauda.
Definição 2 Um chamada de cauda é uma expressão com a cauda, que é uma chamada de procedimento.

(uma cauda chamada recursiva, ou como diz a pesquisa, "auto-chamada de cauda" é um caso especial de uma chamada de cauda, onde o procedimento é chamado a si próprio.)

Ele fornece definições formais para seis diferentes tipos de "máquinas" para avaliar Núcleo do Esquema, onde cada máquina tem o mesmo comportamento observável exceto para o assimptótico espaço complexidade de classe que cada um é.

Por exemplo, depois de dar definições para máquinas com, respectivamente, 1.baseado em pilha de gerenciamento de memória, 2.a coleta de lixo, mas sem cauda chamadas, 3.a coleta de lixo e cauda de chamadas, o papel continua em diante, mesmo com as mais avançadas estratégias de gerenciamento de armazenamento, tais como 4."evlis recursão", onde o ambiente não precisa ser preservado de toda a avaliação do último sub-expressão de argumento em uma chamada de cauda, 5.a redução de um ambiente de encerramento para apenas as variáveis livres de encerramento, e 6.o chamado "seguro-para-espaço" semântica, conforme definido pela Appel e Shao.
A fim de provar que as máquinas pertencem, na verdade, seis espaço distinto complexidade de classes, o papel, para cada par de máquinas em comparação, fornece exemplos concretos de programas que irão expor assintótica espaço de explosão em uma máquina, mas não o outro.

(Ler mais a minha resposta agora, eu não tenho certeza se eu sou conseguiu realmente captar os pontos cruciais da Clinger papel.Mas, infelizmente, eu não posso dedicar mais tempo para desenvolver essa resposta agora.)

A função recursiva é uma função que chama por si só

Ele permite que os programadores escrevam programas eficientes usando um quantidade mínima de código.

A desvantagem é que eles podem causar loops infinitos e outros resultados inesperados se não está escrito corretamente.

Vou explicar tanto Simples função Recursiva e a Cauda função Recursiva

Para escrever um Simples função recursiva

O primeiro ponto a considerar é quando você deve decidir sair do ciclo, que é o caso de loop
A segunda é que o processo se somos nossos próprios de função

A partir do exemplo dado:

public static int fact(int n){
  if(n <=1)
     return 1;
  else 
     return n * fact(n-1);
}

A partir do exemplo acima

if(n <=1)
     return 1;

É o fator decisivo quando para sair do loop

else 
     return n * fact(n-1);

É o processamento a ser feito

Deixe-me a dividir a tarefa, um por um, para facilitar a compreensão.

Vamos ver o que acontece internamente, se eu executar fact(4)

Substituindo n=4

public static int fact(4){
  if(4 <=1)
     return 1;
  else 
     return 4 * fact(4-1);
}

If loop falha, então ele vai para else loop assim, ele retorna 4 * fact(3)

Em memória de pilha, temos 4 * fact(3)

Substituindo n=3

public static int fact(3){
  if(3 <=1)
     return 1;
  else 
     return 3 * fact(3-1);
}

If loop falha, então ele vai para else loop

assim, ele retorna 3 * fact(2)

Lembre-se que o chamado ``4 * fato(3)`

A saída para fact(3) = 3 * fact(2)

Até agora, a pilha tem 4 * fact(3) = 4 * 3 * fact(2)

Em memória de pilha, temos 4 * 3 * fact(2)

Substituindo n=2

public static int fact(2){
  if(2 <=1)
     return 1;
  else 
     return 2 * fact(2-1);
}

If loop falha, então ele vai para else loop

assim, ele retorna 2 * fact(1)

Lembre-se que o chamado 4 * 3 * fact(2)

A saída para fact(2) = 2 * fact(1)

Até agora, a pilha tem 4 * 3 * fact(2) = 4 * 3 * 2 * fact(1)

Em memória de pilha, temos 4 * 3 * 2 * fact(1)

Substituindo n=1

public static int fact(1){
  if(1 <=1)
     return 1;
  else 
     return 1 * fact(1-1);
}

If loop é verdadeiro

assim, ele retorna 1

Lembre-se que o chamado 4 * 3 * 2 * fact(1)

A saída para fact(1) = 1

Até agora, a pilha tem 4 * 3 * 2 * fact(1) = 4 * 3 * 2 * 1

Finalmente, o resultado da fato(4) = 4 * 3 * 2 * 1 = 24

O Recursão seria

public static int fact(x, running_total=1) {
    if (x==1) {
        return running_total;
    } else {
        return fact(x-1, running_total*x);
    }
}

Substituindo n=4

public static int fact(4, running_total=1) {
    if (x==1) {
        return running_total;
    } else {
        return fact(4-1, running_total*4);
    }
}

If loop falha, então ele vai para else loop assim, ele retorna fact(3, 4)

Em memória de pilha, temos fact(3, 4)

Substituindo n=3

public static int fact(3, running_total=4) {
    if (x==1) {
        return running_total;
    } else {
        return fact(3-1, 4*3);
    }
}

If loop falha, então ele vai para else loop

assim, ele retorna fact(2, 12)

Em memória de pilha, temos fact(2, 12)

Substituindo n=2

public static int fact(2, running_total=12) {
    if (x==1) {
        return running_total;
    } else {
        return fact(2-1, 12*2);
    }
}

If loop falha, então ele vai para else loop

assim, ele retorna fact(1, 24)

Em memória de pilha, temos fact(1, 24)

Substituindo n=1

public static int fact(1, running_total=24) {
    if (x==1) {
        return running_total;
    } else {
        return fact(1-1, 24*1);
    }
}

If loop é verdadeiro

assim, ele retorna running_total

A saída para running_total = 24

Finalmente, o resultado da fato(4,1) = 24

Muitas pessoas já explicado recursão aqui.Eu gostaria de citar alguns pensamentos sobre algumas vantagens que a recursividade dá a partir do livro "a Concorrência no .NET, padrões Modernos de concorrentes e programação paralela" por Riccardo Terrell:

"Funcional recursão é o caminho natural para iterar em FP porque evita a mutação do estado.Durante cada iteração, um novo valor é passado para o ciclo construtor em vez de ser actualizado (mutantes).No além disso, uma função recursiva pode ser composto por, tornando o seu programa mais modular, bem como a introdução de oportunidades para explorar paralelização."

Aqui estão algumas notas interessantes de um mesmo livro sobre recursão:

Cauda-chamada de recursão é uma técnica que converte um regular recursiva função em uma versão otimizada que pode lidar com grandes entradas sem riscos e efeitos colaterais.

OBSERVE que A principal razão para uma chamada de cauda como uma otimização é melhorar a localidade de dados, uso de memória, e o uso de cache.Fazendo um rabo chamada, o receptor utiliza o mesmo espaço de pilha do chamador.Isso reduz a pressão de memória.É marginalmente melhora o cache, pois o mesmo a memória é reutilizada para chamadas subsequentes e podem permanecer no cache, em vez de expulsar uma antiga linha de cache para liberar espaço para um novo cache linha.

Um cauda recursiva função é uma função recursiva, onde a última operação que faz antes de voltar é fazer a chamada de função recursiva.Isto é, o valor de retorno da chamada de função recursiva é imediatamente devolvido.Por exemplo, o código teria esta aparência:

def recursiveFunction(some_params):
    # some code here
    return recursiveFunction(some_args)
    # no code after the return statement

Compiladores e interpretadores que implementam chamada de cauda de otimização ou chamada de cauda eliminação pode otimizar o código recursivo para evitar estouros de pilha.Se o seu compilador ou interpretador não implementar tail call optimization (tais como o CPython intérprete) não há benefício adicional ao escrever o seu código dessa forma.

Por exemplo, este é um padrão fatorial recursiva da função em Python:

def factorial(number):
    if number == 1:
        # BASE CASE
        return 1
    else:
        # RECURSIVE CASE
        # Note that `number *` happens *after* the recursive call.
        # This means that this is *not* tail call recursion.
        return number * factorial(number - 1)

E esta é uma chamada de cauda versão recursiva da função fatorial:

def factorial(number, accumulator=1):
    if number == 0:
        # BASE CASE
        return accumulator
    else:
        # RECURSIVE CASE
        # There's no code after the recursive call.
        # This is tail call recursion:
        return factorial(number - 1, number * accumulator)
print(factorial(5))

(Note que, mesmo que este é o código Python, o CPython intérprete não faz chamada de cauda de otimização, de modo a organizar o seu código como este não lhe confere qualquer tempo de execução de benefício.)

Você pode ter para tornar o código um pouco mais ilegível para fazer uso da chamada de cauda de otimização, como mostrado no exemplo fatorial.(Por exemplo, o caso base é agora um pouco intuitivo, e o accumulator parâmetro é efetivamente utilizada como um tipo de variável global.)

Mas o benefício de cauda chamada otimização é que ele impede erros de estouro de pilha.(Eu vou note que você pode obter esse mesmo benefício pela utilização de um algoritmo iterativo, em vez de um recursiva de uma).

Estouros de pilha são causados quando a pilha de chamadas teve muitos objetos de quadro empurrado para.Uma moldura de objeto é empurrado para a pilha de chamadas quando uma função é chamada, e estalou a pilha de chamada quando a função retorna.Moldura de objectos contêm informações tais como variáveis locais e que linha de código para retornar para quando a função retorna.

Se a sua função recursiva faz muitas chamadas recursivas sem retornar, a pilha de chamadas podem exceder o objeto do quadro de limite.(O número varia por plataforma;em Python é 1000 objetos de quadro por padrão.) Isso faz com que uma estouro de pilha erro.(Hey, que é de onde o nome deste site, vem!)

No entanto, se a última coisa que sua função recursiva faz é recursiva chamada e retornar o seu valor de retorno, então não há razão para que ele precisa manter o quadro atual objeto precisa ficar na pilha de chamadas.Afinal, se não há nenhum código após a chamada de função recursiva, não há nenhuma razão para pendurar o quadro atual do objeto de variáveis locais.Para que possamos livrar-se do quadro atual objeto imediatamente, ao invés de mantê-la na pilha de chamadas.O resultado final disso é que a sua pilha de chamadas não cresce em tamanho, e, portanto, não é possível estouro de pilha.

Um compilador ou interpretador deve ter cauda chamada de otimização como um recurso para que ele seja capaz de reconhecer quando a chamada de cauda, a otimização pode ser aplicada.Mesmo assim, você pode ter reorganizar o código em sua função recursiva para fazer uso da chamada de cauda de otimização, e cabe a você se esse potencial diminuição na legibilidade vale a otimização.

Recursão é muito rápido comparado ao normal recursão.É rápido, uma vez que a saída dos antepassados chamada não será escrito na pilha para manter o controle.Mas, em condições normais de recursão todos os ancestral chamadas de saída escrito na pilha para manter o controle.

Licenciado em: CC-BY-SA com atribuição

Não afiliado a StackOverflow