Usarei notação F# para os algoritmos.
1) Algoritmo imperativo, que depende de mutabilidade:
let mutable i = n
let mutable B = ""
while i > 0 do
B <- B + A
i <- i - 1
printf "%A" B
2) Algoritmo recursivo, apenas com valores imutáveis:
let rec concatena A = function
| 1 -> A
| i -> A + concatena A (i-1)
printf "%A" (concatena A n)
3) Algoritmo recursivo com "tail-recursion" (evita stack-overflow) usando
acumulador:
let rec concatena A acc = function
| 0 -> acc
| i -> concatena A (acc + A) (i - 1)
printf "%A" (concatena A "" n)
4) Algoritmo recursivo com "continuation passing style" (evita
stack-overflow):
let rec concatena (A:string) f = function
| 1 -> f A
| i -> concatena A (fun s -> f(A) + s) (i - 1)
printf "%A" (concatena A (fun x -> x) n)
Para quem tem background de C, Pascal, ou derivados ou similares, a solução
1 deve ser a mais óbvia. É aquela que vc diz ao computador exatamente o que
fazer a cada passo, alterando o valor das variáveis (por isso se chama
imperativa).
Mas perceba que a solução 2 é muito mais simples de se compreender. Ela
quebra o problema em 2 problemas: um trivial, e outro reduzido. O trivial é:
concatenar 1 vez é o mesmo que retornar a própria string. O reduzido é:
concatenar n vezes é o mesmo que concatenar A ao resultado da concatenação
de (n-1) vezes.
As soluções 3 e 4 são a mesma coisa que a 2, mas usam duas técnicas
distintas para permitir ao compilador de criar certas otimizações que
impossibilitarão um problema de "stack-overflow" por conta de um grande
número de chamadas recursivas.
A solução 3 usa "tail recursion", isto é, a chamada recursiva é a última
coisa que se faz na função. O compilador pode, nesse caso, transformar essa
chamada recursiva num loop. No final, o código compilado será muito próximo
ao código da solução 1, só que vc pôde obter esse código escrevendo seu
algoritmo duma forma de bem mais alto nível.
A solução 4 usa o que se chama "continuation passing style", isto é, vc
passa à função uma outra função que deve ser chamada assim que a primeira
terminar de executar. Esse talvez seja o mais difícil de "pegar a idéia" pra
quem não está acostumado. Isso só é possível de se fazer de maneira simples
em linguagens "funcionais".
Bruno
--
Bruno FRANÇA DOS REIS
msn: [email protected]
skype: brunoreis666
tel: +55 11 9961-7732
http://brunoreis.com
http://brunoreis.com/tech (en)
http://brunoreis.com/blog (pt)
GPG Key: http://brunoreis.com/bruno-public.key
e^(pi*i)+1=0
2010/4/8 Diogo FN <[email protected]>
> Boa Tarde, pessoal da lista.
>
> Então, me ajuda nessa?
>
> * Dada uma string A e um número N, definir e imprimir uma string B que
> consiste na reprodução da cadeia A, N vezes.
>
> ------------------------------
> Veja quais são os assuntos do momento no Yahoo! + Buscados: Top
> 10<http://br.rd.yahoo.com/mail/taglines/mail/*http://br.maisbuscados.yahoo.com/>-
> Celebridades<http://br.rd.yahoo.com/mail/taglines/mail/*http://br.maisbuscados.yahoo.com/celebridades/>-
> Música<http://br.rd.yahoo.com/mail/taglines/mail/*http://br.maisbuscados.yahoo.com/m%C3%BAsica/>-
> Esportes<http://br.rd.yahoo.com/mail/taglines/mail/*http://br.maisbuscados.yahoo.com/esportes/>
>
