Explorando Recursão e Fractals

Universidade Católica de Petrópolis
Centro de Informática Educativa
Antonio José dos Santos Neto
Bolsista do CNPq/PIBIC
Co-Orientador: Frederico Luis Cabral
Orientador: Silvia Branco Vidal Bustamante
e-mail: cies@risc.ucp.br

Petrópolis- Rio de Janeiro- Brasil

Tema

O tema deste trabalho está voltado para um assunto de grande importância, que consiste em explorar recursão e os fractals.

Com grande aceitação nas áreas de pesquisa e educação, a recursão é centro de várias discussões entre muitos estudiosos sobre a viabilidade de se entender ou não este assunto.

Dicheva, D. (1991 pg. 642), afirma:
 
 

Objetivo

O objetivo deste trabalho é explorar a recursão e os fractals, mostrando as dificuldades de se entender os tipos e características de procedimentos recursivos e também dos procedimentos fractais, tendo em vista que muito pouco tem sido desenvolvido sobre este tema na área de Informática em Educação.

Com base em pesquisas iniciais, este trabalho visa estudar a recursão e suas dificuldades dando ênfase à análise de alguns procedimentos, buscando entender seus significados, e, também estudar o fractal enquanto trabalhado através de estruturas recursivas, procurando entendê-lo e representá-lo através dos recursos computacionais.
 
 

O que é a Recursão ?

Quando se executa um procedimento qualquer e no decorrer de sua execução o computador encontra como sub-procedimento o próprio procedimento executado, diz-se que o mesmo é recursivo, ou seja, recursão é o ato de um procedimento executar a si mesmo.
 

Onde se aplica ?

A recursão é usada em grande escala na área da computação científica, no desenvolvimento de programas do tipo árvores e seus vários estilos, e no estudo dos fractals, o que é de extrema curiosidade científica pois pouco se sabe sobre como construí-los e qual o mecanismo interno de sua construção. Assim sendo normalmente, reproduz-se procedimentos sem entender como eles funcionam. Este projeto se destina a compreendê-los e elucidá-los.

A recursão tem sido também aplicada em sala de aula, onde, através de vários autores (Retzchitzki, 1991; Dicheva, 1991; Müller, 1996a), constata-se grande discussão sobre ser ou não viável ensiná-la para crianças, levando em conta se estas são capazes de entender um processo recursivo.
 

Tipos de recursão

A recursão se apresenta com certa complexidade quando estudada em seus diferentes aspectos. Sabe-se que a recursão se caracteriza como infinita ou finita.

Recursão Infinita

O procedimento recursivo é infinito quando não existe nenhuma condição que faça o procedimento ser interrompido.
 

Recursão Finita

A recursão finita é conhecida quando se encontra uma estrutura de condição de parada em algum momento durante uma execução.

A recursão ainda se apresenta em alguns outros casos. Quando a chamada recursiva aparece no final de um procedimento, dá-se o nome de recursão terminal. Este tipo é de compreensão consideravelmente fácil, pois existe uma maior probabilidade de se prever o que pode acontecer.

Recursão inicial é quando a chamada recursiva se encontra no início do procedimento e central quando se apresenta no meio do módulo. Estas últimas possuem um grau de complexidade bem maior do que a primeira, pois se torna quase que impossível prever o que irá acontecer no término do procedimento (Almeida, 1994), sendo difícil rastreá-lo e entender como se processa cada etapa das chamadas recursivas dentro do mesmo.
 

Recursão Inicial e Central

Neste tipo de recursão, a dificuldade consiste em entender como a chamada recursiva se processa ao nível da relação entre o que se chama em cada nível e como isso é trabalhado pela máquina. Essa dificuldade se reflete também em entender como cada passo da chamada será processado pela inteligência humana.

Dificuldades da recursão

A recursão é tratada por estudantes e professores sob pontos de vista bastante diferentes no que diz respeito à facilidade e dificuldade de se entender este processo. Essas questões podem estar diretamente ligadas ao grau de conhecimento de cada um, visto que se uma pessoa possui uma base computacional relativamente boa, esta terá maior facilidade para entender o processo em si (a execução) e o funcionamento interno do computador para executar a chamada recursiva (conceito de pilha ).

Simplificar a questão afirmando que a recursão pode ser trabalhada por crianças e adolescentes é desconhecer o seu mecanismo intrínseco e a sua complexidade.

Apresentar procedimentos recursivos a crianças e a adolescentes que não tenham pleno domínio do pensamento lógico-formal pode apenas significar pedir-lhes que executem algo que não irão compreender.
 

Fractals
 

Para se buscar a relação entre estruturas recursivas e fractais, no sentido de entendê-las, usa-se o conceito de Fractal, tal como nos é apresentado por Benoit Mandelbrot. De acordo com a definição de Mandelbrot (1991, pg. 207), a geometria fractal é:

De acordo com Graça Pimentel & Maria Cristina (1996) do Instituto de Ciências Matemáticas de São Carlos , tem-se o conceito de pilha:
 
 

A pilha é de extrema importância para se entender um processo recursivo pois se torna simples visualizar as chamadas se esse conceito (pilha) estiver claro para o aluno, como é citado por Ryoti (1996):
 
 

A seguir, será usado, um exemplo do funcionamento da pilha, chamando procedimentos diferentes e portanto não usando ainda procedimentos recursivos.

O procedimento prog1 é o procedimento principal (veja fig.10). No decorrer de sua execução, acontece uma chamada a um outro procedimento (prog2). Nesta hora, é guardado na memória, o endereço da linha do programa onde ocorreu esta chamada, para que quando a execução do prog2 termine, o computador saiba onde ele deve continuar a execução do programa que fez a chamada.

Depois de guardado o endereço de retorno ao programa principal (prog1), o prog2 será executado e do mesmo modo que no prog1, vai acontecer uma chamada a um outro procedimento (prog3). Da mesma forma será guardado o endereço da linha de execução do prog2, e logo depois será executado o prog3. Quando o prog3 chegar ao fim, o computador busca na memória o endereço para retornar ao procedimento que o chamou (prog2), fazendo com que seja executada a linha de programa posterior ao endereço guardado na memória. E assim, terminado o prog2, será resgatado o endereço para retornar ao prog1, também executando a linha deste procedimento, posterior ao endereço guardado na memória, e finalmente terminando a execução do procedimento principal.
 
 
 

Para explicar como funciona a pilha utilizando recursão, serão usados os procedimentos abaixo, que têm a função de exibir na tela os valores que foram colocados na memória em forma de pilha.
 
 
 

to proc2 :cont cs make "p 150 proc :cont end     to proc :cont if not :cont = 0 [proc :cont-1] make "p :p-20 psetxy 0 :p label se [=>>] :cont  end

 

Como já foi analisado anteriormente, na chamada recursiva acontece o mesmo funcionamento, sendo descrito na figura anterior que a diferença está no fato de que a chamada é feita ao próprio procedimento.

Como forma de se esclarecer o conceito de pilha, será analisado detalhadamente o proc2 para se compreender o que se sucede em sua execução.

Como exemplo para análise será executado o proc2 com valor 2 para a variável :cont.

Observe agora, no gráfico a seguir, como as setas indicam as chamadas recursivas, utilizando o conceito de pilha com o valor da variável se alterando a cada chamada :
 

to proc :cont(2) to proc :cont(1) to proc :cont(0)

if not :cont = 0 ~ if not :cont = 0 ~ if not :cont = 0 ~

[ [ [

proc :cont(2) -1 proc :cont(1) -1 proc :cont(0) -1

] ] ]

make "p :p-20 make "p :p-20 make "p :p-20

psetxy 0 :p psetxy 0 :p psetxy 0 :p

label se [=>>] :cont (2) label se [=>>] :cont (1) label se [=>>] :cont (0)

end end end
 
 
 
 

Para facilitar a análise do procedimento, coloca-se o valor da variável cont entre parênteses, e, a cada nova chamada, representa-se novamente o procedimento com o valor da variável cont entre parênteses ao seu lado para, facilitar a visualização a cada nível.

Já na primeira linha do proc existe uma condição de só escrever o valor da variável cont se ele for zero. Caso contrário, o procedimento é novamente executado, porém com o valor da variável cont decrementado uma unidade.

Quando cont estiver com zero, a condição será satisfeita e a execução do procedimento continua normalmente, escrevendo na tela o número zero e, assim finaliza esta chamada retornando para a anterior (retirando o valor da pilha) e executando a linha posterior a que faz a chamada. Dessa forma vai escrevendo até retornar para a primeira chamada e escrevendo o número dois.
 
 

Relacionando estruturas fragmentadas para chegar à fragmentação por chamadas recursivas

O próximo passo é buscar uma relação entre os procedimentos acima tentando visualizar uma característica que seja comum a ambos e dessa forma caminhar em direção a um procedimento único que construa o fractal em qualquer nível desejado.
 

Buscando uma relação entre as duas estruturas:

As setas que estão na frente de cada FD do procedimento fract, indicam a relação entre os dois procedimentos, onde pode-se perceber que cada "bloco" do procedimento fract2 é semelhante ao fract.

Estas setas representam uma situação condicional onde o nível de fragmentação desejado estabeleceria o número de chamadas a um procedimento semelhante, onde a única diferença do original seria a divisão do valor do lado e o decremento de uma variável que indica o nível de cada chamada. Assim dependendo do nível desejado a estrutura elementar seria fragmentada quantas vezes necessário até satisfazer uma condição dada como parâmetro no início do procedimento recursivo.

No esquema acima pode-se observar que: se o nível for zero, o que será realizado será apenas o procedimento elementar.

Se o nível for 1, ele construirá novamente a estrutura elementar, porém com o valor do lado dividido por um número determinado. No exemplo anterior esse número foi três. Desta forma, cada bloco da direita da figura corresponde a uma nova chamada ao procedimento principal (situado à esquerda da figura).

Assim pode-se ir montando um procedimento que ao invés de ter várias instruções passo a passo, as substitua por chamadas recursivas.

Percebe-se que existe um ponto importante envolvendo a construção da figura no nível zero e no nível um, observável tanto nos algoritmos como nas figuras em si:

- Colocando uma figura ao lado da outra nota-se que a diferença entre elas está relacionada com o nível de fragmentação de cada uma; no nível um, em cada lado da estrutura elementar, é construída novamente essa estrutura, porém com o valor de seus lados reduzidos.

A comparação dos algoritmos se permitiu visualizar o ponto de partida para a obtenção do procedimento para se construir o fractal (a partir da figura elementar) que foi a idéia de árvore recursiva.

No esboço feito através de setas, existe realmente uma ligação entre os procedimentos onde é feita uma caracterização das chamadas recursivas através do nível, ou seja, dependendo do nível de fragmentação desejado, dado como parâmetro no início de um procedimento, é que se pode identificar quantas vezes será chamado o próprio procedimento, visto que o computador só irá riscar quando o nível for zero.

Dessa forma enquanto o nível não for igual a zero é chamado novamente o procedimento, decrementando a variável que guarda o valor do nível de fragmentação e dividindo o valor da variável que guarda o lado.

Pode-se perceber que existe uma semelhança da estrutura que se observa acima, com a estrutura de árvore recursiva, o que facilita na busca de um procedimento comum para a construção de fractals.
 
 

Apresentação do procedimento desenvolvido para se obter um fractal, dada sua estrutura elementar
 
 

Considerando a estrutura elementar abaixo e completando o raciocínio que estamos desenvolvendo, pode-se chegar aos fractals abaixo, o que pode significar uma evolução do raciocínio na compreensão de estruturas fractais recursivas.
 

Toma-se a estrutura elementar abaixo
 

Para trabalhar com ela, o procedimento recursivo assim se representa:

to fractal :n :lado

ifelse not :n = 0 [ fractal :n-1 :lado/3] [ fd :lado]

lt 60

ifelse not :n = 0 [ fractal :n-1 :lado/3] [ fd :lado]

rt 120

ifelse not :n = 0 [ fractal :n-1 :lado/3] [ fd :lado]

lt 60

ifelse not :n = 0 [ fractal :n-1 :lado/3] [ fd :lado]

end
 
 

Pode-se observar a estrutura elementar inserida em cada lado da figura.
 
 

FRACTAL 2 100

A figura acima representa o nível 2 de fragmentação.
 
 

FRACTAL 5 100

nível 5 de fragmentação
 
 

Conclusão

Nessa fase inicial do projeto procura-se o entendimento necessário para chegar em um patamar desejado, que se consiga condições de caminhar na direção de uma nova forma de se encarar os problemas que são encontrados quando o assunto é recursão e fractal.

O primeiro passo dado foi procurar simplificar os conceitos básicos relacionados à recursão fazendo uma análise detalhada das características e tipos de processos recursivos que encontra-se na computação.

Busca-se compreender o funcionamento lógico da linguagem apoiando-se em conceitos que leva-se a crescer na vontade de descobrir sempre mais sobre o tema.

Conceitos como o de pilha foram importantes para o processo de entendimento dos tipos complexos de recursão, como a recursão inicial e central e se fez abrir as portas para chegar ao ponto mais importante dessa primeira fase, que foi achar um padrão para a construção de um tipo particular de fractal que na verdade foi uma incógnita durante alguns anos de trabalho.

Este projeto tem como grande meta encontrar um padrão para a construção de qualquer tipo de fractal, e sabe-se que apenas este é o começo de uma longa caminhada e que precisa-se de muito estudo e pesquisa para obter êxito.
 
 

A linguagem LOGO tem sido a principal ferramenta de trabalho. Neste processo tem-se utilizado o LOGO como linguagem de programação, mas tem-se sido orientados por um processo de busca que provem do sistema de idéias vinculados à teoria do conhecimento que envolve o que se chama ambiente LOGO de aprendizagem e que pode caracterizar como estilo LOGO de investigação.

No decorrer deste trabalho procurou-se entender o processamento da recursão ao nível lógico da máquina para entender, em nossa lógica de investigação, como ocorre a chamada recursiva em suas diferentes modalidades.

Entender a relação entre procedimentos recursivos e os fractals foi o passo seguinte do projeto. Descreveu-se no decorrer do trabalho as hipóteses e os encaminhamentos de raciocínio que, uma vez submetidos à verificações no computador, levou a reformular o processo de busca.

Nesse quadro, o sistema de idéias vinculados ao LOGO levou a depurar o procedimento e o próprio raciocínio.

Ao encaminhar-se para níveis mais complexos do trabalho com fractals, a linguagem LOGO apresentou-se lenta e limitada na execução do procedimento, porém, a metodologia de investigação vinculada às idéias do LOGO e à solução de problemas, encaminhou-se para implementar em linguagem de baixo nível, o que se tornava excessivamente demorado através do interpretador LOGO.

Assim, o fractal de Mandelbrot foi possível de ser realizado em tempo bem menor, sem fugir do quadro referencial da investigação, que é buscar a transparência na complexidade dos procedimentos recursivos e das estruturas fractais.

A continuação desse projeto se apresenta bastante promissora, apesar das dificuldades matemáticas e computacionais que este objeto de estudo envolve.
 
 

Considera-se as investigações durante um ano inteiro, apenas como um estudo preliminar, tendo em vista que se caminha em processo de descoberta e não simplesmente de utilização de algoritmos já feitos ou de programas já desenvolvidos. Mediante a beleza, a riqueza e a complexidade do tema e das áreas interdisciplinares a ele relacionadas, pode-se dizer, apesar do caminho percorrido que, de certa forma, este trabalho, começa aqui.

O pensamento que investiga caminha do erro à depuração, da hipótese à reformulação, da obscuridade à clareza. E nesse processo, se desvenda a beleza do conhecimento construído que, como a beleza dos fractals, depende das ações e retroações das estruturas lógicas que se leva ao entendimento.

Aprende-se enquanto se permanece no problema e enquanto se modifica, também recursivamente, como quem volta à questão e vai além dela, talvez construindo pouco a pouco, a parte e o todo, com que de erro em erro e de descoberta em descoberta, se desenha a própria existência humana.
 

Bibliografia
 

ABELSON, H e ANDREA DI SESSA. (1981) Turtle Geometry: the computer as a medium for exploring mathematics, Mit Press, Massachussets

ALMEIDA, F. B. (1996) Análise e Dificuldades da Recursão Simples e Avançada II. Universidade Católica de Petrópolis, PIBIC/ CNPq.

DICHEVA, D. (1991) How to introduce recursion in LOGO. Parma, ASI.

DICHEVA, D. and CLOSE, S. (1993) Misconceptions and mental models of recursion . Athens, Doukas School.

DUPUIS, C. et alii ( 1991) Situations recursives en LOGO: mettant en evidence des conceptions erronees , in LOGO et Aprentissages, Paris, Délachaux et Niestle.

PIMENTEL, G. & CRISTINA, M.( 1997 ) Exemplo do Uso de Pilhas,

URL: http://www.icmsc.sc.usp.br/manuals/sce182/pexemp.html

KERN, J. (1991) Mandelbrot Sweep of the Koch Snowflake. LOGO Exchange, vol. 1, nº 6 ISTE Oregon

MANDELBROT, B. (1991) Objectos Fractais, Ed. Gradiva

MULLER, J. (1996a) The recurring question of recursion. LOGO Exchange vol. 14, nº 3. ISTE, Oregon

MULLER, J. (1996b) Recursion, the problem solver. LOGO Exchange vol. 14, nº 3. ISTE, Oregon.

NETO, A. J. & CABRAL, F. L. (1997) Explorando Recursão e Fractals. Universidade Católica de Petrópolis, PIBIC/ CNPq.

NICHOLLS, P. (1998) Using Biology to Help Understand Recursion, URL: www.csc.liv.ac.ok/~biocomp/notes/recursion/article.html.

NOSS, R, and HOYLES, C. (1991) Deus pas en avant, deux pas en arrière. in LOGO et aprentissages, Paris, Délachaux et Niestle.

PAPERT, S. (1985) LOGO: Computadores e Educação. SP, Ed. Brasiliense.

PELLEGRINO, C. and MALARA (1991) LOGO in the teaching of mathematics, Parma, ASI.

PETERSON, W. e BRANDERHORST, T. (1992) The Waite Group Fractais para Windows, Berkeley Brasil Editora.

RETSCHITZKI, J. (1991) Apprentissage de la récursivité et métacognition: les apports de l’intelligence artificielle et de la psychologie cognitive in LOGO et apprentissages, Ed. Délachaux et Niestlé, Paris.

RYOTI, D. E. (1996) Recursion and the Stack LOGO Exchange Volume 15, number 1.

VALENTE, J. V. & VALENTE, A. B. (1988) Logo, Conceitos e Aplicações, SP, Ed. Mc Graw Hill.

VITALE, B. (1989 ) Elusive Recursion: a trip in recursive land in New Ideas in Psychol. Vol 7 Nº 3.