Compreender como funcionam as funções recursivas

Como o título explica, tenho uma questão de programação muito fundamental que ainda não consegui entender. Filtrando todos os (extremamente inteligentes) "Para entender a recursão, você deve primeiro entender a recursão." respostas de vários tópicos online que ainda não estou entendendo.

Compreendendo que, quando nos deparamos com não saber o que não sabemos, podemos tender a fazer as perguntas erradas ou fazer as perguntas certas incorretamente, irei compartilhar o que eu "acho" que minha pergunta é na esperança de que alguém com uma perspectiva semelhante possa compartilhar alguns um pouco de conhecimento que vai ajudar a ligar a lâmpada recursiva para mim!

Aqui está a função (a sintaxe é escrita em Swift):

func sumInts(a: Int, b: Int) -> Int {
    if (a > b) {
        return 0
    } else {
        return a + sumInts(a: a + 1, b: b)
    }
}

Usaremos 2 e 5 como nossos argumentos:

println(sumInts(a: 2, b: 5))

Obviamente, a resposta é 14. Mas não tenho certeza de como esse valor é alcançado.

Estes são meus 2 hangups:

1. A função é chamada recursivamente até que uma condição seja atendida. Essa condição é a> b. Quando essa condição for atendida, retorne 0. À primeira vista, eu esperaria que o valor de retorno fosse 0, o que é obviamente incorreto.

2. Imprimir o valor de 'a' em cada iteração produz um valor que eu esperaria: 2, 3, 4, 5 (em que ponto 5 + 1> b que atende a primeira condição: a> b), mas ainda não t veja como o valor de 14 é alcançado.

Meu primeiro pensamento é que algo semelhante ao seguinte está acontecendo magicamente:

var answer = a;
answer += a+1 until a > b;
return answer;   

Então, descartando magia, não estou conseguindo nada. Eu adoraria entender o que está acontecendo mais do que apenas implicitamente.

Se alguém pudesse gentilmente explicar o que acontece tecnicamente durante esse tipo de função e por que o resultado não é 0 e como, eventualmente,, a + sumInts(a: a + 1, b: b) = 14eu ficaria para sempre em dívida com você.

Acho que a confusão está em pensar nisso como "a mesma função" sendo chamada muitas vezes. Se você pensar nisso como "muitas cópias da mesma função sendo chamada", então pode ser mais claro:

Apenas uma cópia da função retorna 0, e não é a primeira (é a última). Portanto, o resultado de chamar o primeiro não é 0.

Para a segunda parte da confusão, acho que será mais fácil explicar a recursão em inglês. Leia esta linha:

return a + sumInts(a + 1, b: b)

como "retorna o valor de 'a' mais (o valor de retorno de outra cópia da função, que é o valor da cópia de 'a' mais (o valor de retorno de outra cópia da função, que é o valor da segunda cópia de ' a 'mais (... ", com cada cópia da função gerando uma nova cópia de si mesma com um aumentado em 1, até que a condição a> b seja atendida.

No momento em que você atinge a condição a> b sendo verdadeira, você tem uma longa pilha (potencialmente arbitrária) de cópias da função, todas no meio da execução, todas aguardando o resultado da próxima cópia para descobrir o que elas deve adicionar a 'a'.

(editar: também, algo a estar ciente é que a pilha de cópias da função que mencionei é uma coisa real que ocupa memória real e irá travar seu programa se ficar muito grande. O compilador pode otimizá-lo em alguns casos, mas esgotar o espaço da pilha é uma limitação significativa e infeliz das funções recursivas em muitas linguagens)

1. A função é chamada recursivamente até que uma condição seja atendida. Essa condição é a > b. Quando essa condição for atendida, retorne 0. À primeira vista, eu esperaria que o valor de retorno fosse 0, o que é obviamente incorreto.

Aqui está o que a computação do computador sumInts(2,5)pensaria se fosse capaz de:

I want to compute sumInts(2, 5)
for this, I need to compute sumInts(3, 5)
and add 2 to the result.
  I want to compute sumInts(3, 5)
  for this, I need to compute sumInts(4, 5)
  and add 3 to the result.
    I want to compute sumInts(4, 5)
    for this, I need to compute sumInts(5, 5)
    and add 4 to the result.
      I want to compute sumInts(5, 5)
      for this, I need to compute sumInts(6, 5)
      and add 5 to the result.
        I want to compute sumInts(6, 5)
        since 6 > 5, this is zero.
      The computation yielded 0, therefore I shall return 5 = 5 + 0.
    The computation yielded 5, therefore I shall return 9 = 4 + 5.
  The computation yielded 9, therefore I shall return 12 = 3 + 9.
The computation yielded 12, therefore I shall return 14 = 2 + 12.

Como você pode ver, alguma chamada para a função sumIntsna verdade retorna 0, porém este não é o valor final porque o computador ainda tem que adicionar 5 a esse 0, então 4 ao resultado, então 3, então 2, conforme descrito pelas quatro últimas sentenças de os pensamentos do nosso computador. Observe que, na recursão, o computador não precisa apenas calcular a chamada recursiva, mas também se lembrar do que fazer com o valor retornado pela chamada recursiva. Existe uma área especial da memória do computador chamada stack onde este tipo de informação é salvo, este espaço é limitado e funções muito recursivas podem esgotar a stack: este é o stack overflow que dá seu nome ao nosso site mais querido.

Sua declaração parece fazer a suposição implícita de que o computador esquece onde estava ao fazer uma chamada recursiva, mas não esquece, é por isso que sua conclusão não corresponde à sua observação.

2. Imprimir o valor de 'a' em cada iteração produz um valor que eu esperaria: 2, 3, 4, 5 (em que ponto 5 + 1> b que atende a primeira condição: a> b), mas eu ainda não vejo como o valor de 14 é alcançado.

Isso ocorre porque o valor de retorno não é aele mesmo, mas a soma do valor de ae do valor retornado pela chamada recursiva.

Para entender a recursão, você deve pensar no problema de uma maneira diferente. Em vez de uma grande sequência lógica de etapas que faz sentido como um todo, você pega um grande problema e divide em problemas menores e os resolve, uma vez que você tenha uma resposta para os subproblemas, você combina os resultados dos subproblemas para fazer o solução para o problema maior. Pense em você e seus amigos precisando contar o número de bolas de gude em um balde enorme. Cada um de vocês pega um balde menor e vai contá-los individualmente e, quando terminar, você soma os totais. Bem, agora, se cada um de vocês encontrar algum amigo e dividir os baldes ainda mais, então você só precisa esperar que esses outros amigos calcule os totais, traga de volta para cada um de vocês, some. E assim por diante.

Você deve se lembrar que toda vez que a função se chama recursivamente, ela cria um novo contexto com um subconjunto do problema, uma vez que essa parte seja resolvida, ela é retornada para que a iteração anterior possa ser concluída.

Deixe-me mostrar as etapas:

sumInts(a: 2, b: 5) will return: 2 + sumInts(a: 3, b: 5)
sumInts(a: 3, b: 5) will return: 3 + sumInts(a: 4, b: 5)
sumInts(a: 4, b: 5) will return: 4 + sumInts(a: 5, b: 5)
sumInts(a: 5, b: 5) will return: 5 + sumInts(a: 6, b: 5)
sumInts(a: 6, b: 5) will return: 0

uma vez que sumInts (a: 6, b: 5) foi executado, os resultados podem ser calculados, voltando para cima na cadeia com os resultados que você obtém:

 sumInts(a: 6, b: 5) = 0
 sumInts(a: 5, b: 5) = 5 + 0 = 5
 sumInts(a: 4, b: 5) = 4 + 5 = 9
 sumInts(a: 3, b: 5) = 3 + 9 = 12
 sumInts(a: 2, b: 5) = 2 + 12 = 14.

Outra forma de representar a estrutura da recursão:

 sumInts(a: 2, b: 5) = 2 + sumInts(a: 3, b: 5)
 sumInts(a: 2, b: 5) = 2 + 3 + sumInts(a: 4, b: 5)  
 sumInts(a: 2, b: 5) = 2 + 3 + 4 + sumInts(a: 5, b: 5)  
 sumInts(a: 2, b: 5) = 2 + 3 + 4 + 5 + sumInts(a: 6, b: 5)
 sumInts(a: 2, b: 5) = 2 + 3 + 4 + 5 + 0
 sumInts(a: 2, b: 5) = 14 

A recursão é um tópico complicado de entender e não acho que posso fazer justiça aqui. Em vez disso, tentarei me concentrar na parte específica do código que você tem aqui e tentarei descrever a intuição de por que a solução funciona e a mecânica de como o código calcula seu resultado.

O código que você forneceu aqui resolve o seguinte problema: você deseja saber a soma de todos os inteiros de a a b, inclusive. Para o seu exemplo, você quer a soma dos números de 2 a 5, inclusive, que é

2 + 3 + 4 + 5

Ao tentar resolver um problema recursivamente, uma das primeiras etapas deve ser descobrir como dividir o problema em um problema menor com a mesma estrutura. Suponha que você queira somar os números de 2 a 5, inclusive. Uma maneira de simplificar isso é observar que a soma acima pode ser reescrita como

2 + (3 + 4 + 5)

Aqui, (3 + 4 + 5) passa a ser a soma de todos os inteiros entre 3 e 5, inclusive. Em outras palavras, se você quiser saber a soma de todos os inteiros entre 2 e 5, comece calculando a soma de todos os inteiros entre 3 e 5 e, em seguida, some 2.

Então, como você calcula a soma de todos os inteiros entre 3 e 5, inclusive? Bem, essa soma é

3 + 4 + 5

que pode ser pensado em vez de

3 + (4 + 5)

Aqui, (4 + 5) é a soma de todos os inteiros entre 4 e 5, inclusive. Portanto, se você quisesse calcular a soma de todos os números entre 3 e 5, inclusive, calcularia a soma de todos os inteiros entre 4 e 5 e, em seguida, adicionaria 3.

Existe um padrão aqui! Se você deseja calcular a soma dos inteiros entre a e b, inclusive, você pode fazer o seguinte. Primeiro, calcule a soma dos inteiros entre a + 1 e b, inclusive. Em seguida, adicione a a esse total. Você notará que "calcular a soma dos inteiros entre a + 1 e b, inclusive" é praticamente o mesmo tipo de problema que já estamos tentando resolver, mas com parâmetros ligeiramente diferentes. Em vez de calcular de a a b, inclusive, estamos computando de a + 1 a b, inclusive. Essa é a etapa recursiva - para resolver o problema maior ("soma de a para b, inclusive"), reduzimos o problema a uma versão menor dele mesmo ("soma de a + 1 para b, inclusive.").

Se você der uma olhada no código acima, perceberá que há esta etapa nele:

return a + sumInts(a + 1, b: b)

Este código é simplesmente uma tradução da lógica acima - se você quiser somar de a a b, inclusive, comece somando a + 1 a b, inclusive (essa é a chamada recursiva para sumInts) e, em seguida, adicionea .

Claro, essa abordagem por si só não funcionará. Por exemplo, como você calcularia a soma de todos os inteiros entre 5 e 5, inclusive? Bem, usando nossa lógica atual, você calcularia a soma de todos os inteiros entre 6 e 5, inclusive, e depois adicionaria 5. Então, como você calcula a soma de todos os inteiros entre 6 e 5, inclusive? Bem, usando nossa lógica atual, você calcularia a soma de todos os inteiros entre 7 e 5, inclusive, e depois adicionaria 6. Você notará um problema aqui - isso continua e continua!

Na resolução recursiva de problemas, deve haver uma maneira de parar de simplificar o problema e, em vez disso, ir resolvê-lo diretamente. Normalmente, você encontrará um caso simples onde a resposta pode ser determinada imediatamente e, em seguida, estruture sua solução para resolver casos simples diretamente quando eles surgirem. Isso é normalmente chamado de caso base ou base recursiva .

Então, qual é o caso básico neste problema específico? Quando você está somando inteiros de a a b, inclusive, se a for maior que b, então a resposta é 0 - não há números no intervalo! Portanto, estruturaremos nossa solução da seguinte maneira:

1. Se a> b, a resposta é 0.
2. Caso contrário (a ≤ b), obtenha a resposta da seguinte forma:
   1. Calcule a soma dos inteiros entre a + 1 e b.
   2. Adicione um para obter a resposta.

Agora, compare este pseudocódigo com o seu código real:

func sumInts(a: Int, b: Int) -> Int {
    if (a > b) {
        return 0
    } else {
        return a + sumInts(a + 1, b: b)
    }
}

Observe que há quase exatamente um mapa um para um entre a solução delineada no pseudocódigo e este código real. O primeiro passo é o caso básico - no caso de você pedir a soma de um intervalo vazio de números, você obtém 0. Caso contrário, calcule a soma entre a + 1 e b e, em seguida, adicione a.

Até agora, dei apenas uma ideia de alto nível por trás do código. Mas você tinha duas outras perguntas muito boas. Primeiro, por que isso nem sempre retorna 0, visto que a função diz para retornar 0 se a> b? Em segundo lugar, de onde vêm os 14? Vamos dar uma olhada nisso.

Vamos tentar um caso muito, muito simples. O que acontece se você ligar sumInts(6, 5)? Nesse caso, rastreando o código, você vê que a função retorna apenas 0. Essa é a coisa certa a se fazer, para - não há nenhum número no intervalo. Agora, tente algo mais difícil. O que acontece quando você liga sumInts(5, 5)? Bem, aqui está o que acontece:

1. Você liga sumInts(5, 5). Nós caímos noelse ramo, que retorna o valor de `a + sumInts (6, 5).
2. Para sumInts(5, 5)determinar o que sumInts(6, 5)é, precisamos pausar o que estamos fazendo e ligar para sumInts(6, 5).
3. sumInts(6, 5)é chamado. Ele entra na ifagência e retorna 0. No entanto, essa instância de sumIntsfoi chamada por sumInts(5, 5), portanto, o valor de retorno é comunicado de volta sumInts(5, 5), não para o chamador de nível superior.
4. sumInts(5, 5)agora pode calcular 5 + sumInts(6, 5)para voltar 5. Em seguida, ele o retorna para o chamador de nível superior.

Observe como o valor 5 foi formado aqui. Começamos com uma chamada ativa para sumInts. Isso disparou outra chamada recursiva, e o valor retornado por essa chamada comunicou a informação de volta para sumInts(5, 5). A chamada para sumInts(5, 5)then, por sua vez, fez alguns cálculos e retornou um valor ao chamador.

Se você tentar fazer isso sumInts(4, 5), eis o que acontecerá:

• sumInts(4, 5)tenta voltar 4 + sumInts(5, 5). Para fazer isso, ele chamasumInts(5, 5) .
  • sumInts(5, 5)tenta voltar 5 + sumInts(6, 5). Para fazer isso, ele chamasumInts(6, 5) .
  • sumInts(6, 5)retorna 0 de volta para sumInts(5, 5).</li> <li>sumInts (5, 5) now has a value forsumInts (6, 5) , namely 0. It then returns5 + 0 = 5`.
• sumInts(4, 5)agora tem um valor para sumInts(5, 5), a saber, 5. Ele então retorna 4 + 5 = 9.

Em outras palavras, o valor retornado é formado pela soma dos valores um de cada vez, cada vez pegando um valor retornado por uma chamada recursiva específica sumIntse adicionando o valor atual de a. Quando a recursão chega ao fundo, a chamada mais profunda retorna 0. No entanto, esse valor não sai imediatamente da cadeia de chamadas recursivas; em vez disso, ele apenas devolve o valor para a chamada recursiva uma camada acima dela. Dessa forma, cada chamada recursiva apenas adiciona mais um número e o retorna mais acima na cadeia, culminando com a soma geral. Como exercício, tente rastrear isso sumInts(2, 5), que é o que você queria para começar.

Espero que isto ajude!

Você tem algumas boas respostas aqui até agora, mas vou adicionar mais uma que tem uma abordagem diferente.

Em primeiro lugar, escrevi muitos artigos sobre algoritmos recursivos simples que você pode achar interessantes; Vejo

http://ericlippert.com/tag/recursion/

http://blogs.msdn.com/b/ericlippert/archive/tags/recursion/

Esses estão na ordem mais recente no topo, então comece de baixo.

Em segundo lugar, até agora todas as respostas descreveram a semântica recursiva considerando a ativação da função . Cada uma, cada chamada, faz uma nova ativação , e a chamada recursiva é executada no contexto desta ativação. Essa é uma boa maneira de pensar sobre isso, mas há outra forma equivalente: pesquisa e substituição de texto inteligente .

Deixe-me reescrever sua função em uma forma um pouco mais compacta; não pense nisso como sendo em um idioma específico.

s = (a, b) => a > b ? 0 : a + s(a + 1, b)

Espero que faça sentido. Se você não está familiarizado com o operador condicional, ele tem a formacondition ? consequence : alternative e seu significado ficará claro.

Agora queremos avaliar s(2,5) Fazemos isso substituindo textualmente a chamada pelo corpo da função e, em seguida, substituindo apor 2e bpor 5:

s(2, 5) 
---> 2 > 5 ? 0 : 2 + s(2 + 1, 5)

Agora avalie o condicional. Nós substituímos textualmente 2 > 5por false.

---> false ? 0 : 2 + s(2 + 1, 5)

Agora substitua textualmente todas as condicionais falsas pela alternativa e todas as condicionais verdadeiras pela consequência. Temos apenas condicionais falsos, então nós substituímos textualmente essa expressão pela alternativa:

---> 2 + s(2 + 1, 5)

Agora, para evitar que eu tenha que digitar todos esses +sinais, substitua textualmente a aritmética constante por seu valor. (Isso é meio que uma trapaça, mas não quero ter que controlar todos os parênteses!)

---> 2 + s(3, 5)

Agora pesquise e substitua, desta vez com o corpo da chamada, 3pora e 5por b. Colocaremos a substituição da chamada entre parênteses:

---> 2 + (3 > 5 ? 0 : 3 + s(3 + 1, 5))

E agora continuamos fazendo as mesmas etapas de substituição textual:

---> 2 + (false ? 0 : 3 + s(3 + 1, 5))  
---> 2 + (3 + s(3 + 1, 5))                
---> 2 + (3 + s(4, 5))                     
---> 2 + (3 + (4 > 5 ? 0 : 4 + s(4 + 1, 5)))
---> 2 + (3 + (false ? 0 : 4 + s(4 + 1, 5)))
---> 2 + (3 + (4 + s(4 + 1, 5)))
---> 2 + (3 + (4 + s(5, 5)))
---> 2 + (3 + (4 + (5 > 5 ? 0 : 5 + s(5 + 1, 5))))
---> 2 + (3 + (4 + (false ? 0 : 5 + s(5 + 1, 5))))
---> 2 + (3 + (4 + (5 + s(5 + 1, 5))))
---> 2 + (3 + (4 + (5 + s(6, 5))))
---> 2 + (3 + (4 + (5 + (6 > 5 ? 0 : s(6 + 1, 5)))))
---> 2 + (3 + (4 + (5 + (true ? 0 : s(6 + 1, 5)))))
---> 2 + (3 + (4 + (5 + 0)))
---> 2 + (3 + (4 + 5))
---> 2 + (3 + 9)
---> 2 + 12
---> 14

Tudo o que fizemos aqui foi apenas uma substituição textual direta . Na verdade, eu não deveria ter substituído "3" por "2 + 1" e assim por diante até que fosse necessário, mas pedagogicamente teria ficado difícil de ler.

A ativação de função nada mais é do que substituir a chamada de função pelo corpo da chamada e substituir os parâmetros formais por seus argumentos correspondentes. Você tem que ter cuidado ao introduzir parênteses de forma inteligente, mas fora isso, é apenas uma substituição de texto.

Claro, a maioria dos idiomas não implementa realmente a ativação como substituição de texto, mas logicamente é isso que é.

Então, o que é uma recursão ilimitada? Uma recursão onde a substituição textual não para! Observe como finalmente chegamos a uma etapa em que não havia mais o sque substituir e poderíamos então apenas aplicar as regras da aritmética.

A maneira como normalmente descubro como uma função recursiva funciona é olhando para o caso base e trabalhando de trás para frente. Aqui está a técnica aplicada a esta função.

Primeiro, o caso básico:

sumInts(6, 5) = 0

Em seguida, a chamada logo acima na pilha de chamadas :

sumInts(5, 5) == 5 + sumInts(6, 5)
sumInts(5, 5) == 5 + 0
sumInts(5, 5) == 5

Em seguida, a chamada logo acima na pilha de chamadas:

sumInts(4, 5) == 4 + sumInts(5, 5)
sumInts(4, 5) == 4 + 5
sumInts(4, 5) == 9

E assim por diante:

sumInts(3, 5) == 3 + sumInts(4, 5)
sumInts(3, 5) == 3 + 9
sumInts(3, 5) == 12

E assim por diante:

sumInts(2, 5) == 2 + sumInts(3, 5)
sumInts(4, 5) == 2 + 12
sumInts(4, 5) == 14

Observe que chegamos à nossa chamada original para a função sumInts(2, 5) == 14

A ordem em que essas chamadas são executadas:

sumInts(2, 5)
sumInts(3, 5)
sumInts(4, 5)
sumInts(5, 5)
sumInts(6, 5)

A ordem em que essas chamadas retornam:

sumInts(6, 5)
sumInts(5, 5)
sumInts(4, 5)
sumInts(3, 5)
sumInts(2, 5)

Observe que chegamos a uma conclusão sobre como a função opera rastreando as chamadas na ordem em que retornam .

Eu vou tentar.

Executando a equação a + somas (a + 1, b), mostrarei como a resposta final é 14.

//the sumInts function definition
func sumInts(a: Int, b: Int) -> Int {
    if (a > b) {
        return 0
    } else {
        return a + sumInts(a + 1, b)
    }
}

Given: a = 2 and b = 5

1) 2 + sumInts(2+1, 5)

2) sumInts(3, 5) = 12
   i) 3 + sumInts(3+1, 5)
   ii) 4 + sumInts(4+1, 5)
   iii) 5 + sumInts(5+1, 5)
   iv) return 0
   v) return 5 + 0
   vi) return 4 + 5
   vii) return 3 + 9

3) 2 + 12 = 14.

Deixe-nos saber se você tiver mais perguntas.

Aqui está outro exemplo de funções recursivas no exemplo a seguir.

Um homem acabou de se formar na faculdade.

t é a quantidade de tempo em anos.

O número real total de anos trabalhados antes de se aposentar pode ser calculado da seguinte forma:

public class DoIReallyWantToKnow 
{
    public int howLongDoIHaveToWork(int currentAge)
    {
      const int DESIRED_RETIREMENT_AGE = 65;
      double collectedMoney = 0.00; //remember, you just graduated college
      double neededMoneyToRetire = 1000000.00

      t = 0;
      return work(t+1);
    }

    public int work(int time)
    {
      collectedMoney = getCollectedMoney();

      if(currentAge >= DESIRED_RETIREMENT_AGE 
          && collectedMoney == neededMoneyToRetire
      {
        return time;
      }

      return work(time + 1);
    }
}

E isso deve ser apenas o suficiente para deprimir qualquer um, lol. ;-P

Recursão. Em Ciência da Computação, a recursão é abordada em profundidade no tópico Autômatos Finitos.

Em sua forma mais simples, é uma referência própria. Por exemplo, dizer que "meu carro é um carro" é uma afirmação recursiva. O problema é que a afirmação é uma recursão infinita, pois nunca terá fim. A definição na declaração de um "carro" é que ele é um "carro", portanto pode ser substituído. No entanto, não há fim porque no caso de substituição, continua a ser "o meu carro é um carro".

Isso poderia ser diferente se a declaração fosse "meu carro é um bentley. Meu carro é azul". Nesse caso, a substituição do carro na segunda situação poderia ser "bentley", resultando em "meu bentley é azul". Esses tipos de substituições são explicados matematicamente em Ciência da Computação por meio de Gramáticas Livres de Contexto .

A substituição real é uma regra de produção. Dado que a afirmação é representada por S e que carro é uma variável que pode ser um "bentley", esta afirmação pode ser reconstruída recursivamente.

S -> "my"S | " "S | CS | "is"S | "blue"S | ε
C -> "bentley"

Isso pode ser construído de várias maneiras, pois cada uma |significa que há uma escolha. Spode ser substituído por qualquer uma dessas opções e S sempre começa vazio. Os εmeios para encerrar a produção. Assim como Spodem ser substituídas, outras variáveis ​​também podem (há apenas uma e éC que representaria "bentley").

Então, começar Svazio e substituí-lo pela primeira escolha "my"S Storna-se

"my"S

Sainda pode ser substituído, pois representa uma variável. Poderíamos escolher "meu" novamente, ou ε para encerrá-lo, mas vamos continuar fazendo nossa declaração original. Nós escolhemos o espaço que significa que Sé substituído por" "S

"my "S

Em seguida, vamos escolher C

"my "CS

E C só tem uma escolha para substituição

"my bentley"S

E o espaço novamente para S

"my bentley "S

E assim por diante "my bentley is"S, "my bentley is "S, "my bentley is blue"S,"my bentley is blue" (substituindo S para ε termina a produção) e nós recursivamente construímos a nossa declaração "meu Bentley é azul".

Pense na recursão como essas produções e substituições. Cada etapa do processo substitui seu antecessor para produzir o resultado final. No exemplo exato da soma recursiva de 2 a 5, você acaba com a produção

S -> 2 + A
A -> 3 + B
B -> 4 + C
C -> 5 + D
D -> 0

Isso se torna

2 + A
2 + 3 + B
2 + 3 + 4 + C
2 + 3 + 4 + 5 + D
2 + 3 + 4 + 5 + 0
14

Acho que a melhor maneira de entender funções recursivas é perceber que elas são feitas para processar estruturas de dados recursivas. Mas em sua função original sumInts(a: Int, b: Int)que calcula recursivamente a soma dos números de aa b, parece não ser uma estrutura de dados recursiva ... Vamos tentar uma versão ligeiramente modificada sumInts(a: Int, n: Int)em nque quantos números você adicionará.

Agora, sumInts é recursivo n, um número natural. Ainda não é um dado recursivo, certo? Bem, um número natural pode ser considerado uma estrutura de dados recursiva usando os axiomas de Peano:

enum Natural = {
    case Zero
    case Successor(Natural)
}

Portanto, 0 = Zero, 1 = Sucessor (Zero), 2 = Sucessor (Sucessor (Zero)) e assim por diante.

Depois de ter uma estrutura de dados recursiva, você tem o modelo para a função. Para cada caso não recursivo, você pode calcular o valor diretamente. Para os casos recursivos, você assume que a função recursiva já está funcionando e a usa para calcular o caso, mas desconstruindo o argumento. No caso do Natural, significa que em vez de Succesor(n)usaremos n, ou, equivalentemente, em vez de nusaremos n - 1.

// sums n numbers beginning from a
func sumInts(a: Int, n: Int) -> Int {
    if (n == 0) {
        // non recursive case
    } else {
        // recursive case. We use sumInts(..., n - 1)
    }
}

Agora, a função recursiva é mais simples de programar. Primeiro, o caso básico n=0,. O que devemos retornar se não quisermos adicionar números? A resposta é, claro, 0.

E o caso recursivo? Se quisermos adicionar nnúmeros começando com ae já tivermos uma sumIntsfunção de trabalho que funcione para n-1? Bem, precisamos adicionara e invocar sumIntscom a + 1, então terminamos com:

// sums n numbers beginning from a
func sumInts(a: Int, n: Int) -> Int {
    if (n == 0) {
        return 0
    } else {
        return a + sumInts(a + 1, n - 1)
    }
}

O bom é que agora você não precisa mais pensar no baixo nível de recursão. Você só precisa verificar se:

• Para os casos básicos dos dados recursivos, ele calcula a resposta sem usar recursão.
• Para os casos recursivos de dados recursivos, ele calcula a resposta usando a recursão sobre os dados desestruturados.

Você pode estar interessado na implementação de funções de Nisan e Schocken . O pdf vinculado faz parte de um curso online gratuito. Ele descreve a segunda parte de uma implementação de máquina virtual em que o aluno deve escrever um compilador de linguagem de máquina virtual para linguagem de máquina. A implementação da função que eles propõem é capaz de recursão porque é baseada em pilha.

Para apresentar a implementação da função: Considere o seguinte código de máquina virtual:

Se o Swift compilou para essa linguagem de máquina virtual, o seguinte bloco de código Swift:

mult(a: 2, b: 3) - 4

compilaria para

push constant 2  // Line 1
push constant 3  // Line 2
call mult        // Line 3
push constant 4  // Line 4
sub              // Line 5

A linguagem da máquina virtual é projetada em torno de uma pilha global .push constant ncoloca um número inteiro nesta pilha global.

Depois de executar as linhas 1 e 2, a pilha se parece com:

256:  2  // Argument 0
257:  3  // Argument 1

256e 257são endereços de memória.

call mult coloca o número da linha de retorno (3) na pilha e aloca espaço para as variáveis ​​locais da função.

256:  2  // argument 0
257:  3  // argument 1
258:  3  // return line number
259:  0  // local 0

... e vai para a gravadora function mult. O código interno multé executado. Como resultado da execução desse código, calculamos o produto de 2 e 3, que é armazenado na 0ª variável local da função.

256:  2  // argument 0
257:  3  // argument 1
258:  3  // return line number
259:  6  // local 0

Pouco antes de returnsair de mult, você notará a linha:

push local 0  // push result

Vamos colocar o produto na pilha.

256:  2  // argument 0
257:  3  // argument 1
258:  3  // return line number
259:  6  // local 0
260:  6  // product

Quando voltamos, acontece o seguinte:

• Coloque o último valor da pilha no endereço de memória do 0º argumento (256 neste caso). Este é o lugar mais conveniente para colocá-lo.
• Descarte tudo na pilha até o endereço do 0º argumento.
• Vá para o número da linha de retorno (3 neste caso) e avance.

Depois de retornar, estamos prontos para executar a linha 4, e nossa pilha se parece com isto:

256:  6  // product that we just returned

Agora colocamos 4 na pilha.

256:  6
257:  4

subé uma função primitiva da linguagem da máquina virtual. Ele recebe dois argumentos e retorna seu resultado no endereço usual: o do 0º argumento.

Agora temos

256:  2  // 6 - 4 = 2

Agora que você sabe como funciona uma chamada de função, é relativamente simples entender como funciona a recursão. Sem mágica , apenas uma pilha.

Implementei sua sumIntsfunção nesta linguagem de máquina virtual:

function sumInts 0     // `0` means it has no local variables.
  label IF
    push argument 0
    push argument 1
    lte              
    if-goto ELSE_CASE
    push constant 0
    return
  label ELSE_CASE
    push constant 2
    push argument 0
    push constant 1
    add
    push argument 1
    call sumInts       // Line 15
    add                // Line 16
    return             // Line 17
// End of function

Agora vou chamá-lo de:

push constant 2
push constant 5
call sumInts           // Line 21

O código é executado e chegamos ao ponto de parada onde lteretorna false. É assim que a pilha se parece neste ponto:

// First invocation
256:  2   // argument 0
257:  5   // argument 1
258:  21  // return line number
259:  2   // augend
// Second
260:  3   // argument 0
261:  5   // argument 1
262:  15  // return line number
263:  3   // augend
// Third
264:  4   // argument 0
265:  5   // argument 1
266:  15  // return line number
267:  4   // augend
// Fourth
268:  5   // argument 0
269:  5   // argument 1
270:  15  // return line number
271:  5   // augend
// Fifth
272:  6   // argument 0
273:  5   // argument 1
274:  15  // return line number
275:  0   // return value

Agora vamos "desenrolar" nossa recursão. return0 e vá para a linha 15 e avance.

271:  5
272:  0

Linha 16: add

271:  5

Linha 17: return5 e vá para a linha 15 e avance.

267:  4
268:  5

Linha 16: add

267:  9

Linha 17: return9 e vá para a linha 15 e avance.

263:  3
264:  9

Linha 16: add

263:  12

Linha 17: return12 e vá para a linha 15 e avance.

259:  2
260:  12

Linha 16: add

259:  14

Linha 17: return14 e vá para a linha 21 e avance.

256:  14

Aí está. Recursão: glorificado goto.

Uma dica muito boa que descobri ao aprender e realmente entender a recursão é passar algum tempo aprendendo uma linguagem que não tenha nenhuma forma de construção de loop além da recursão. Dessa forma, você terá uma boa ideia de como USE a recursão por meio da prática.

Eu segui http://www.htdp.org/ que, além de ser um tutorial de Scheme, também é uma ótima introdução sobre como projetar programas em termos de arquitetura e design.

Mas, basicamente, você precisa investir algum tempo. Sem uma compreensão "firme" de recursão, certos algoritmos, como retrocesso, sempre parecerão "difíceis" ou mesmo "mágicos" para você. Portanto, persevere. :-D

Espero que isso ajude e boa sorte!

Já existem muitas respostas boas. Ainda estou tentando.
Quando chamada, uma função obtém um espaço de memória alocado, que é empilhado no espaço de memória da função do chamador. Neste espaço de memória, a função mantém os parâmetros passados ​​a ela, as variáveis ​​e seus valores. Este espaço de memória desaparece junto com a chamada de retorno final da função. Conforme a ideia de pilha continua, o espaço de memória da função do chamador agora se torna ativo.

Para chamadas recursivas, a mesma função obtém vários espaços de memória empilhados uns sobre os outros. Isso é tudo. A ideia simples de como a pilha funciona na memória de um computador deve ajudar você a entender como a recursão acontece na implementação.

Um pouco fora do assunto, eu sei, mas ... tente procurar recursão no Google ... Você verá por exemplo o que significa :-)

As versões anteriores do Google retornavam o seguinte texto (citado de memória):

Recursão

Veja recursão

Em 10 de setembro de 2014, a piada sobre recursão foi atualizada:

Recursão

Você quis dizer: Recursion

Para outra resposta, veja esta resposta .

Pense na recursão como múltiplos clones fazendo a mesma coisa ...

Você pede para clonar [1]: "some números entre 2 e 5"

+ clone[1]               knows that: result is 2 + "sum numbers between 3 and 5". so he asks to clone[2] to return: "sum numbers between 3 and 5"
|   + clone[2]           knows that: result is 3 + "sum numbers between 4 and 5". so he asks to clone[3] to return: "sum numbers between 4 and 5"
|   |   + clone[3]       knows that: result is 4 + "sum numbers between 5 and 5". so he asks to clone[4] to return: "sum numbers between 5 and 5"
|   |   |   + clone[4]   knows that: result is 5 + "sum numbers between 6 and 5". so he asks to clone[5] to return: "sum numbers between 6 and 5"
|   |   |   |   clone[5] knows that: he can't sum, because 6 is larger than 5. so he returns 0 as result.
|   |   |   + clone[4]   gets the result from clone[5] (=0)  and sums: 5 + 0,  returning 5
|   |   + clone[3]       gets the result from clone[4] (=5)  and sums: 4 + 5,  returning 9
|   + clone[2]           gets the result from clone[3] (=9)  and sums: 3 + 9,  returning 12
+ clone[1]               gets the result from clone[2] (=12) and sums: 2 + 12, returning 14

e voilá !!

Muitas das respostas acima são muito boas. Uma técnica útil para resolver a recursão, porém, é definir primeiro o que queremos fazer e codificar como um humano faria. No caso acima, queremos somar uma sequência de inteiros consecutivos (usando os números acima):

2, 3, 4, 5  //adding these numbers would sum to 14

Agora, observe que essas linhas são confusas (não erradas, mas confusas).

if (a > b) {
    return 0 
}

Por que o teste a>b? E por quereturn 0

Vamos mudar o código para refletir mais de perto o que um ser humano faz

func sumInts(a: Int, b: Int) -> Int {
  if (a == b) {
    return b // When 'a equals b' I'm at the most Right integer, return it
  }
  else {
    return a + sumInts(a: a + 1, b: b)
  }
}

Podemos fazer isso de forma ainda mais humana? Sim! Normalmente somamos da esquerda para a direita (2 + 3 + ...). Mas a recursão acima está somando da direita para a esquerda (... + 4 + 5). Altere o código para refleti-lo ( -pode ser um pouco intimidante, mas não muito)

func sumInts(a: Int, b: Int) -> Int {
  if (a == b) {
    return b // When I'm at the most Left integer, return it
  }
  else {
    return sumInts(a: a, b: b - 1) + b
  }
}

Alguns podem achar esta função mais confusa, já que estamos começando da extremidade 'distante', mas praticar pode fazer com que pareça natural (e é outra boa técnica de 'pensamento': tentar 'ambos' os lados ao resolver uma recursão). E novamente, a função reflete o que um humano (a maioria?) Faz: obtém a soma de todos os inteiros à esquerda e adiciona o 'próximo' inteiro à direita.

Eu estava tendo dificuldade em entender a recursão, então eu encontrei este blog e já vi essa pergunta, então pensei que deveria compartilhar. Você deve ler este blog. Achei extremamente útil explicar com pilha e até mesmo explicar como duas recursões funcionam com pilha passo a passo. Eu recomendo que você primeiro entenda como a pilha funciona, o que explica muito bem aqui: jornada para a pilha

then now you will understand how recursion works now take a look of this post: Entenda a recursão passo a passo

É um programa:

def hello(x):
    if x==1:
        return "op"
    else:
        u=1
        e=12
        s=hello(x-1)
        e+=1
        print(s)
        print(x)
        u+=1
    return e

hello(3)

A recursão começou a fazer sentido para mim quando parei de ler o que os outros dizem sobre ela ou de vê-la como algo que posso evitar e apenas escrevi o código. Encontrei um problema com uma solução e tentei duplicar a solução sem olhar. Eu só olhei para a solução quando fiquei completamente preso. Então voltei a tentar duplicá-lo. Fiz isso novamente em vários problemas até desenvolver meu próprio entendimento e senso de como identificar um problema recursivo e resolvê-lo. Quando cheguei a este nível, comecei a inventar problemas e resolvê-los. Isso me ajudou mais. Às vezes, as coisas só podem ser aprendidas experimentando você mesmo e lutando; até que você “pegue”.

Deixe-me contar um exemplo da série Fibonacci, Fibonacci é

t (n) = t (n - 1) + n;

se n = 0, então 1

então vamos ver como funciona a recursão, eu só substituir nem t(n)com n-1e assim por diante. parece:

t (n-1) = t (n - 2) + n + 1;

t (n-1) = t (n - 3) + n + 1 + n;

t (n-1) = t (n - 4) + n + 1 + n + 2 + n;

.

.

.

t (n) = t (nk) + ... + (nk-3) + (nk-2) + (nk-1) + n;

sabemos se t(0)=(n-k)é igual a 1então, n-k=0então n=ksubstituímos kpor n:

t (n) = t (nn) + ... + (n-n + 3) + (n-n + 2) + (n-n + 1) + n;

se omitirmos n-nentão:

t (n) = t (0) + ... + 3 + 2 + 1 + (n-1) + n;

o mesmo 3+2+1+(n-1)+nacontece com o número natural. calcula comoΣ3+2+1+(n-1)+n = n(n+1)/2 => n²+n/2

o resultado para fib é: O(1 + n²) = O(n²)

Esta é a melhor maneira de entender a relação recursiva