Duvida sobre recursividade

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 213, 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 213=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 163=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 113 = 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.

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

Beleza!! :)

Abraço

^^ 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.

É bem isso mesmo ^^

E com prática vai ficando mais fácil

Abraço