Recursão ou Algoritmos Recursivos

Ir em baixo

Recursão ou Algoritmos Recursivos

Mensagem por Evandro Abu Kamel em Sex 25 Set 2009, 13:39

Um método comum de simplificação é dividir o problema em subproblemas do mesmo tipo. Como técnica de programação, este método é conhecido como dividir e conquistar e é a chave para a construção de muitos algoritmos importantes, bem como uma parte fundamental da programação dinâmica.

Neste link está a história de Martin e o Dragão:
http://www.dcc.ufam.edu.br/~ruiter/icc/martin0.html

A recursão na programação é bem exemplificada quando uma função é definida em termos de si mesma. Um exemplo da aplicação da recursão são os parsers (analisadores gramaticais) para linguagens de programação. Uma grande vantagem da recursão é que um conjunto infinito de sentenças possíveis, designs ou outros dados podem ser definidos, analisados ou produzidos por um programa de computador finito.

Relações de recorrência são equações que definem uma ou mais seqüências recursivamente. Alguns tipos específicos de relações de recorrência podem ser “resolvidos” para que se obtenha uma definição não-recursiva.

Um exemplo clássico de recursão é a definição da função fatorial, dada aqui em pseudocódigo:

Código:
função fatorial(n)
{
  se (n <= 1)
    retorne 1;
  senão
    retorne n * fatorial(n-1);
}

A função chama a si mesma recursivamente em uma versão menor da entrada (n - 1) e multiplica o resultado da chamada por n, até que alcance o caso base, de modo análogo à definição matemática de fatorial.

Um exemplo de algoritmo recursivo é o procedimento que “processa” (faz alguma coisa com) todos os nós de uma árvore:

Código:
procedimento ProcessarArvore(no)
{
  ProcessarNo(no);    // realiza a operação específica com o nó primeiramente fornecido
  paracada no_filho de no faça ProcessarArvore(no_filho);
}

Isso aí é uma introdução a algoritmos recursivos.
Segue abaixo a implementação da lista recursiva.

Lista Recursiva Simples:
Código:
using System;
using System.Collections.Generic;
using System.Text;

namespace Lista_Rec
{
    class Lista
    {
        public int head;
        public Lista tail;

        public Lista(int h, Lista t)
        {
            this.head = h;
            this.tail = t;
        }

        public static Lista cons(int x, Lista L)
        {
            return new Lista(x, L);
        }

        public static Lista append(Lista L, int x)
        {
            // adiciona um elemento ao final da lista
            if (L == null)
            {
                Console.WriteLine("Inserindo elemento {0}", x);
                return cons(x, null);
            }
            else
            {
                Lista R = append(L.tail, x);
                return cons(L.head, R);
            }
        }

        public static Lista filtraPares(Lista L)
        {
            // filtra os elementos pares da lista
            if (L == null)
                return null;
            else
            {
                int h = L.head;
                Lista t = L.tail;
                Lista R = filtraPares(t);
                if (h % 2 == 0)
                    return cons(h, R);  // eh par
                else
                    return R; // eh impar
            }
        }

        public static int soma(Lista L)
        {
            // soma todos os elementos da lista
            if (L == null)
                return 0;
            else
                return L.head + soma(L.tail);
        }

        public static void print(Lista L)
        {
            // imprime a lista
            if (L != null)
            {
                Console.Write("  {0}", L.head);
                print(L.tail);
            }
            else
                Console.WriteLine("");
        }


        /* ***************************************
        *      PROGRAMA PRINCIPAL
        * *************************************** */

        static void Main(string[] args)
        {
            Lista L = cons(1, cons(2, cons(5, null)));
            Lista LQ;
            int maior;

            Console.WriteLine("\nA lista esta assim:");
            print(L);

            Console.WriteLine("\nA soma dos elementos eh: {0}", soma(L));

            L = append(L, 8);
            L = append(L, 11);
            L = append(L, 16);

            Console.WriteLine("\nA lista esta assim:");
            print(L);
            Console.ReadLine();

            L = append(L, 5);
            L = append(L, 7);
            L = append(L, 9);
            Console.WriteLine("\nA lista esta assim:");
            print(L);

            Console.ReadLine();
        }
    }
}

Até mais. Cool

_________________
"Faça as coisas o mais simples que você puder,
porém, não as mais simples." Albert Einstein

avatar
Evandro Abu Kamel
Administrador
Administrador

Número de Mensagens : 222
Idade : 29
Data de inscrição : 11/03/2009

Ver perfil do usuário http://forum.clubedosistema.com

Voltar ao Topo Ir em baixo

Re: Recursão ou Algoritmos Recursivos

Mensagem por Marden em Qui 08 Out 2009, 18:56

Pessoal, deixo linkado ums slides, do meu amigo Paulo Feofiloff, que podem ajudar muito vocês em AEDII.

Algoritmos em C - Paulo Feofiloff

Abraço.

Marden
Membro
Membro

Número de Mensagens : 1
Data de inscrição : 28/03/2009

Ver perfil do usuário

Voltar ao Topo Ir em baixo

Voltar ao Topo


 
Permissão deste fórum:
Você não pode responder aos tópicos neste fórum