Esse problema está focado principalmente no algoritmo, talvez algo abstrato e mais acadêmico.
O exemplo está oferecendo um pensamento, quero uma maneira genérica; portanto, o exemplo é usado apenas para nos tornar mais claros sobre seus pensamentos.
De um modo geral, um loop pode ser convertido em recursivo.
por exemplo:
for(int i=1;i<=100;++i){sum+=i;}
E a recursiva relacionada é:
int GetTotal(int number)
{
if (number==1) return 1; //The end number
return number+GetTotal(number-1); //The inner recursive
}
E, finalmente, para simplificar isso, é necessário um recursivo de cauda:
int GetTotal (int number, int sum)
{
if(number==1) return sum;
return GetTotal(number-1,sum+number);
}
No entanto, a maioria dos casos não é tão fácil de responder e analisar. O que eu quero saber é:
1) Podemos obter uma "maneira geral comum" de converter um loop (por / enquanto ...) em um recursivo? E em que tipos de coisas devemos prestar atenção ao fazer a conversão? Seria melhor escrever informações detalhadas com algumas amostras e suas teorias de persudo, além do processo de conversão.
2) "Recursivo" tem duas formas: Linearmente recursivo e Tail-Recursivo. Então, qual é o melhor para converter? Que "regra" devemos dominar?
3) Às vezes, precisamos manter o "histórico" do recursivo, isso é facilmente feito em uma declaração de loop:
por exemplo:
List<string> history = new List<string>();
int sum=0;
for (int i=1;i<=100;++i)
{
if(i==1) history.Add(i.ToString()+"'s result is:1.");
else
{
StringBuilder sub = new StringBuilder();
for(int j=1;j<=i;++j)
{
if(j==i) sbu.Append(j.ToString());
else
{
sub.Append(j.ToString()+"+");
}
}
sum +=i;
sbu.Append("'s result is:"+sum+Environment.NewLine);
}
}
O resultado abaixo é:
O resultado de 1 é 1.
O resultado de 1 + 2 é 3.
O resultado de 1 + 2 + 3 é 6 …………
No entanto, acho difícil manter o histórico de forma recursiva, porque um algoritmo recursivo se concentra em obter o último resultado e fazer um retorno de chamada. Portanto, tudo isso é feito através da pilha mantida pela linguagem de programação que atribui memória automaticamente na forma de pilha. E como podemos "manualmente" remover cada um dos "valores da pilha" e retornar vários valores por meio de um algoritmo recursivo?
E o que dizer "de um algoritmo recursivo a um loop"? Eles podem ser convertidos um para o outro (acho que deve ser feito teoricamente, mas quero coisas mais precisas para provar meus pensamentos) .
fonte
Respostas:
Na verdade, você deve dividir a função primeiro:
Um loop tem algumas partes:
o cabeçalho e o processamento antes do loop. Pode declarar algumas novas variáveis
a condição, quando parar o loop.
o corpo do loop real. Altera algumas das variáveis do cabeçalho e / ou os parâmetros passados.
a calda; o que acontece após o loop e retornar o resultado.
Ou para escrever:
Usar esses blocos para fazer uma chamada recursiva é bem direto:
Et voilà; uma versão recursiva final de qualquer loop.
break
s econtinue
s no corpo do loop ainda terão que ser substituídosreturn tail
e retornadosfoo_recursion(params, modified_header_vars)
conforme necessário, mas isso é bastante simples.Indo para o outro lado é mais complicado; em parte porque pode haver várias chamadas recursivas. Isso significa que cada vez que colocamos um quadro de pilha, pode haver vários locais onde precisamos continuar. Também pode haver variáveis que precisamos salvar na chamada recursiva e nos parâmetros originais da chamada.
Podemos usar uma opção para solucionar isso:
fonte
Seguindo a resposta do @ratchet freak, criei este exemplo de como a função Fibonacci pode ser reescrita para um loop while em Java. Observe que há uma maneira muito mais simples (e eficiente) de reescrever o Fibonacci com um loop while.
fonte