Duvida sobre recursividade

[keven1406 2]

Pessoal, pesquisei bastante e ainda estou pesquisando por ai sobre essas duas duvidas. Estou estudando pelo livro JavaScript Eloquent - uma moderna introdução ao JavaScript. Ainda sou iniciante e quando chegou na parte de recursividade fiquei com algumas duvidas.

1º - duvida: Sabendo que uma pilha de chamadas agrupa as funções por ordem de chamada, e depois desfaz delas também por ordem. Quando usamos recursividade, é criado uma nova função, tipo uma copia da função anterior, ou a mesma função é alterada com os novos valores dos parâmetros? Para esclarecer: Estou modificando a mesma função ou os valores da função que estou retornando são novos valores?

2º - Fiquei com essa duvida depois de ver esse código que me deixou pensando por horas:

Considere este quebra-cabeça: iniciando com o número 1 e repetidamente adicionando 5 ou multiplicando por 3, uma infinita quantidade de novos números pode ser produzida. Como você implementaria uma função que, dado um número, tenta achar a sequência de adições e multiplicações que produzem esse número? Por exemplo, o número 13 pode ser produzido multiplicando-se por 3 e adicionando-se 5 duas vezes. Já o número 15 não pode ser produzido de nenhuma forma.

function findSolution(target){
function find(start,history){
if (start == target)
return history;
else if (start>target)
return null;
else
return find(start + 5, "("+ history+"+5)") || find(start *3, "("+history+"*3)");
}
return find(1,"1");
}
console.log(findSolution(24));

O resultado é esse: (((1*3)+5)*3)

Fiquei com duvida porque quando chega em um determinado momento da repetição, em que não tem como o primeiro valor de find(start+"("+history+"+5) dar o resultado correto, ele volta para o resultado da repetição anterior e começa a calcula novamente.

Estou com um nó na cabeça. Vou colocar a parte do livro aqui para vocês darem uma olhada:

Para entender melhor como essa função produz o resultado que estamos esperando, vamos analisar todas as chamadas a find que são feitas quando procuramos a solução para o número 13.

find(1, “1”)  find(6, “(1 + 5)”)    find(11, “((1 + 5) + 5)”)      find(16, “(((1 + 5) + 5) + 5)”)         too big      find(33, “(((1 + 5) + 5) * 3)”) //Minha duvida: Como ele volta para o valor 11 para calcular o 11*3 e dar 33???        too big    find(18, “((1 + 5) * 3)”)      too big  find(3, “(1 * 3)”)    find(8, “((1 * 3) + 5)”)      find(13, “(((1 * 3) + 5) + 5)”)        found!Pessoal, me perdoem se saiu muito dificiu de entender. Estou desesperado. Será que não vou conseguir passar dessa linha? Estou pesquisando em tudo que é lugar.

OBS: Não estou fazendo curso, estudo sozinho com base nos livros.

[AndersonMamede 88]

1) Recursividade não necessariamente cria nem altera funções, apenas executa - podendo passar ou não parâmetros. Mas se dentro da função que será chamada várias vezes você criar uma outra função, então cada vez que ela for executada será criada uma nova função porque você fez ela criar. O exemplo que você mostrou não cria várias funções, porque na verdade a função que é executada várias vezes é find, e ela apenas faz comparações e chama ela novamente (recursão). Já as variáveis utilizadas dentro da função (exemplo: start), por serem privadas, serão criadas novamente a cada execução, mas cada vez será em um contexto diferente; será no contexto da execução da função, ou seja, cada chamada/execução terá sua própria variável start. Essas variáveis existirão enquanto a execução da chamada que a criou não finalizar; isto quer dizer que, por exemplo, a variável start criada na primeira execução da find só será removida quando a execução que a criou completar totalmente, e por ter sido a primeira a ser chamada (nesse exemplo), essa variável só será removida no final da execução da pilha.

Recursão é como se você criasse uma função, e depois chamasse ela várias vezes seguidas, uma embaixo da outra, mas com recursão a ordem de execução é diferente pois é uma pilha: a última função chamada será a primeira a ser completamente executada, depois a penúltima, etc, até chegar à primeira chamada original. Veja a imagem abaixo:

2) O que acontece é que quando a função é chamada novamente por causa da recursão, exemplo wash(count=3), ela irá chamar wash(count=2) antes de terminar sua execução. Ou seja, começa a execução de wash(count=3), no meio para a execução para chamar wash(count=2), e a mesma coisa acontece com wash(count=2) para chamar wash(count=1).

No código que você mostrou, a função find pode ser (e será em alguns casos) chamada duas vezes, isso porque tem o "||" ("ou"). Ou seja, quando a primeira parte (que é find(start + 5, "("+ history+"+5)")) retornar um valor que seja interpretado como false (ex: false, "", 0, null, etc), a segunda parte (find(start *3, "("+history+"*3)")) será chamada. Isso quer dizer que quando a variável start for maior que a variável target, a segunda parte começará a ser chamada (por causa do return null).

Essa análise de execução que você colocou não está completa. A análise completa é essa:

find(1, "1")

  find(6, "(1 + 5)")

    find(11, "((1 + 5) + 5)")

      find(16, "(((1 + 5) + 5) + 5)")

        find(21, "((((1 + 5) + 5) + 5) + 5)")

          find(26, "(((((1 + 5) + 5) + 5) + 5) + 5)")

            find(63, "(((((1 + 5) + 5) + 5) + 5) * 3)")

              find(48, "((((1 + 5) + 5) + 5) * 3)")

                find(33, "(((1 + 5) + 5) * 3)")

                  find(18, "((1 + 5) * 3)")

                    find(23, "(((1 + 5) * 3) + 5)")

                      find(28, "((((1 + 5) * 3) + 5) + 5)")

                        find(69, "((((1 + 5) * 3) + 5) * 3)")

                          find(54, "(((1 + 5) * 3) * 3)")

                            find(3, "(1 * 3)")

                              find(8, "((1 * 3) + 5)")

                                find(13, "(((1 * 3) + 5) + 5)")

                                  find(18, "((((1 * 3) + 5) + 5) + 5)")

                                    find(23, "(((((1 * 3) + 5) + 5) + 5) + 5)")

                                      find(28, "((((((1 * 3) + 5) + 5) + 5) + 5) + 5)")

                                        find(69, "((((((1 * 3) + 5) + 5) + 5) + 5) * 3)")

                                          find(54, "(((((1 * 3) + 5) + 5) + 5) * 3)")

                                            find(39, "((((1 * 3) + 5) + 5) * 3)")

                                              find(24, "(((1 * 3) + 5) * 3)")

Quando o start chega ao 26 e fica maior que o target (que é 24), a função retorna null (por causa do if(start>target)); nisso a segunda parte (depois do "||") é executada. Nesse momento, o start atual é 21, pois foi o valor que chamou o find(21+5 = 26). Então find é chamada na segunda parte usando 21*3, que dá 63 e que também é maior que target, o que também retorna null e também faz a segunda parte ser chamada. No momento que deu 21*3=63, o valor de start era 21, e o valor de start que originou o 21 foi 16 (16+5=21); sendo assim, quando a segunda parte do 16 for chamada, vai dar 16*3=48 e também retornar null, pois é maior que target; o valor que originou o 16 foi 11 (11+5=16), então a segunda parte é chamada usando o valor 11, o que resulta em 11*3 = 33. E assim vai, até que o valor correto seja encontrado ou todas as execuções terminem.

É como se as chamadas fossem assim:

obs1: o que está após "//" é como o comando é interpretado;

obs2: removi o segundo parâmetro para ficar mais fácil de visualizar

-> find(1+5); // find(6)

    -> find(6+5); // find(11)

        -> find(11+5); // find(16)

            -> find(16+5); // find(21)

                -> find(21+5); // find(26) => null

                // aqui o start é 26, fica maior que target e é retornado null, fazendo com que a

                // segunda parte seja chamada

                return find(21*3); // find(63) => null

                // por 63 também ser maior que target, também é retornado null; como já é a segunda

                // parte e não há mais para a função fazer, ela termina a execução enviando o

                // retorno null para a chamada que originou a atual, onde o start era 16 (16+5=21),

                // e faz com que a segunda parte dela seja executada;

            return find(16*3); // find(48) => null

            // como a primeira parte do 16 retornou null, agora a segunda parte é executada, ou

            // seja, 16*3, que também retorna null, enviando o retorno null para a chamada que

            // originou a atual, onde start era 11 (11+5=16);

        return find(11*3); // find(33) => null

        // também retorna null, e acontece a mesma coisa que no caso anterior

    return find(6*3); // find(18)

    // aqui o start é 18 e é menor que o target, o que volta a fazer com que a primeira parte seja

    // executada, onde soma +5 e resulta em 23;

    -> find(18+5); // find(23)

        -> find(23+5); // find(28) => null

        return find(23*3); // find(69) => null

    return find(18*3); // find(54) => null

return find(1*3); // find(3)

-> find(3+5); // find(8)

    -> find(8+5); // find(13)


    // e assim segue a execução: quando o resultado da soma +5 for maior que target (24), a segunda

    // parte será executada, multiplicando start por *3; quando o valor na segunda parte também for

    // maior que target, então é retornado null para a chamada anterior (que originou a atual), etc;

Não sei de deu para entender, é meio complicado explicar. Use a análise completa para seguir o raciocínio com esse código:

function findSolution(target){

    function find(start,history){

        console.info('find('+start+', "'+history+'")');


        if (start == target)

            return history;

        else if (start>target)

            return null;

        else

            return  find(start + 5, "("+ history+" + 5)") || find(start *3, "("+history+" * 3)");

    }

    return find(1,"1");

}

console.log(findSolution(24));

Acho que a melhor maneira de entender isso é estudando, treinando e analisando a execução.

[keven1406 2]

Muito obrigado. Você conseguiu tirar minha duvida com uma explicação muito boa! Vou estudar e treinar mais.

[AndersonMamede 88]

Beleza!! :)

Abraço

[keven1406 2]

^^ O interessante é que tudo ocorre como uma mola. O programa atenta encontrar por diversas rotas o resultado e quando não resolve retorna null, fazendo com o que programa pegue a outra rota para mais uma vez esticar a mola até onde der. Quando o resultado é encontrado, ele vai retornando por todo caminho até chegar no ponto de origem e mostrar o resultado no console. Muito bom e novamente obrigado.

[AndersonMamede 88]

É bem isso mesmo ^^

E com prática vai ficando mais fácil

Abraço