Recursão

Podemos encontrar referências a processos recursivos datadas de 700 AC.

Em 1202, Leonardo Pisano Bigollo ( filho de bonacci, Fibonacci), em Liber Abaci propõe o uso dos algoritmos hindu-arábicos que usamos hoje e a sequência numérica que recebeu seu nome: $F_0=1,F_2=1$ e $F_n = F_{n-1}+F_{n-2}$, enquanto estudava a reprodução de coelhos.

No final do século XIX Grassmann e Pierce usaram a recursão para definir a adição, a multiplicação e para provar as propriedades de associatividade, distributividade e comutatividade, destas operações.

Em 1934 Gödel atualiza as definições de Jacques Herbrand introduzindo a generalização do conceito de funções recursivas.

A funções recursivas são uma classe de funções no domínio dos números naturais, estudadas em teoria da computação, que receberam este nome devido ao processo de recursão segundo o qual o valor de uma função é definido pela aplicação da mesma função a partes cada vez menores do problema.

Tomemos por exemplo uma função para o cálculo do fatorial de um número $x$ representado por $x!$. Neste caso, uma função $fatorial(x)$ deverá devolver o produto $1 \times 2 \times 3... \times x$ para todo $x > 0$ e $1$ para $x=0$. Observe que podemos representar esta função usando dois casos distintos e recursão: $$ \begin{array}{lcl} fatorial(0) & = & 1 \\ fatorial(x) & = & x \times fatorial(x-1) \end{array} $$

$x!$ é calculado por $1 \times 2 \times 3... \times x$ para todo $x > 0$ e $1$ para $x=0$. Que pode ser representado recursivamente por: $$ \begin{array}{lcl} fatorial(0) & = & 1 \\ fatorial(x) & = & x \times fatorial(x-1) \end{array} $$

Sendo assim, para calcular o fatorial de $4$ teremos $fatorial(4) = 24$

$fatorial(4)= 4 \times fatorial(3)$

$fatorial(4)= 4 \times (3 \times fatorial(2))$

$fatorial(4)= 4 \times (3 \times (2 \times fatorial(1)))$

$fatorial(4)= 4 \times (3 \times (2 \times (1 \times fatorial(0))))$

$fatorial(4)= 4 \times (3 \times (2 \times (1 \times 1))) = 24$

A definição do cálculo do fatorial por meio de: $$ \begin{array}{lcl} fatorial(0) & = & 1 \\ fatorial(x) & = & x \times fatorial(x-1) \end{array} $$ Explicita um algoritmo para o cálculo do fatorial de um número inteiro e positivo.

Um algoritmo é uma forma efetiva de resolver um problema que pode ser executada por uma pessoa, ou máquina, em um número finito de passos.

Foi esta classe de funções recursivas, general recursive functions, que caracterizou o primeiro modelo matemático para a definição de computabilidade, sendo anterior, e equivalente, a Máquina de Turing.

Podemos definir função recursiva como: uma função que chama a si mesmo, para resolver uma versão menor da sua tarefa, até uma chamada final que não requer que a função chame a si mesmo.

Em funções recursivas é indispensável que exista um Caso Base, uma condição terminal, onde a aplicação da função, não requeira outra chamada recursiva. Sob pena de cair em um conjunto infinito de chamadas.

Uma forma de encontrar o caso base é pensar primeiro no caso mais simples, e depois generalizar o problema. No caso da função fatorial nosso caso base é: $fatorial(0) = 1$. E a generalização está determinada por: $fatorial(x) = x \times fatorial(x-1)$. Podemos ver isso em Haskell.

Escreva uma função para o cálculo do fatorial de um número inteiro positivo, utilizando Haskell, ou qualquer outra linguagem de programação, desde que nesta linguagem você use uma função lambda para esta tarefa. Você tem 15 minutos para isso.

Lógicos: $==$, $/=$, $>,<,<=,>=$, $\&\&,||$: Ex. $a == b$

Aritmético: $+,-,*,/$: Ex. $3 * 8$

Potência: ^, ^^, **: Ex. $4$ ^^$(-4)$

Funções: $abs$, $quot$, $rem$ ou $div$, $mod$: Ex. $quot \space \space 8 \space \space 5$ ou $8 \space \space `quot` \space \space 5$

Sequência: $..$: Ex. $[1..10]$ ou $[a..z]$ nunca $[10..1]$

Um dos primeiros algoritmos documentados é o algoritmo para o cálculo do Maior Divisor Comum (MDC) de Euclides publicado por volta do ano 300 AC. Podemos simplificar este algoritmo dizendo que dados dois inteiros $A$ e $B$, o MDC entre eles será dado pelo valor absoluto de $A$ se $B=0$ e pelo MDC entre $B$ e o resto da divisão de $A$ por $B$ se $B>0$.

Escreva uma função para o cálculo do MDC entre dois números inteiros positivos, usando o algoritmo de Euclides conforme apresentado aqui, utilizando Haskell.

Escreva uma função recursiva que dado um número inteiro $n$, devolva a soma dos dígitos deste número. Exemplo: dado 1234 a função deverá devolver 10. Utilizando Haskell.

Estrutura de dados que representa um conjunto homogêneo sequencialmente ordenados.

A estrutura primitiva da lista é a lista vazia representada por [].

O operador $:$ é o construtor de listas. Este é um operador polimórfico, dado por: $$>:type (:):: a -> [a] -> [a]$$

As listas são construídas com elementos do mesmo tipo.

Todas as listas são formadas de dois elementos, recursivamente.

Função $head$ devolve o primeiro elemento de uma lista;

Função $tail$ devolve todos os elementos da lista menos o primeiro;

$head [a,b,c,d] = a$ e $tail [a,b,c,d] = [b,c,d]$

Função $last$ devolve o último elemento de uma lista;

Função $init$ devolve todos os elementos da lista menos o último;

$last [a,b,c,d] = d$ e $init [a,b,c,d] = [a,b,c]$

Listas podem ser criadas usando o operador de sequência: $ [limiteInferior .. limiteSuperior] $

Podemos formar as listas escrevendo os termos desejados: $ [1otermo, 2otermo .. limiteSuperior] $

Expressões criadas a partir de elementos da teoria dos conjuntos: $$F = { E(x) | x ∈ C ∧ P1(x) ∧ . . . ∧ Pn(x) }$$

Que em Haskell: $$F = [ E(x) | x \leftarrow lista, P1(x), ... , Pn(x) ]$$

Por Exemplo, temos o conjunto: $$A = { x^2|X \in N}$$

Em Haskell: $$listaQuad = [ x^2 | x \leftarrow [1..30] ]$$

Escreva uma função recursiva que dado um string determine se este string é um palíndromo, ou não. Utilizando Haskell.