Recursividade

Recursividade

Recursividade é o ato de uma função chamar a si mesma.

Função Fatorial

Uma função que calcule o fatorial de um número inteiro n (simbolizado por n!) é um bom exemplo de uma função recursiva.

Por exemplo:

0! = 1
1! = 1
2! = 2 . 1 = 2
3! = 3 . 2 . 1 = 6
4! = 4 . 3 . 2 . 1 = 24
5! = 5 . 4 . 3 . 2 . 1 = 120

Desta forma, posso expressar:

1! = 1 . 0!
2! = 2 . 1!
3! = 3 . 2!
4! = 4 . 3!
5! = 5 . 4!

Note que, nos exemplos acima, que:

n! = n . (n - 1)!

Função em C para calcular o fatorial de um número inteiro n

#include <stdio.h>
int fatorial(int n) 
{
  if (n <= 1)
    return 1;
  else
    return n * fatorial(n-1);
}

int main()
{
    int a;
    printf("\nEntre com um valor inteiro :");
    scanf("%d",&a);
    printf("O fatorial de %d é %d\n\n",a,fatorial(a));
    return(0);
}

Multiplicação de dois números naturais

Outro exemplo de recursividade pode ser obtido na multiplicação de dois números naturais. O produto a * b pode ser obtido como a somado a si mesmo b vezes. Esta multiplicação pode ser implementada por um programa interativo. Uma definição recursiva equivalente é.:

a * b = 0 se b = 0
a * b = a se b = 1
a * b = a * (b - 1) + a se b > 1

Exercício

Implemente uma função recursiva para multiplicar dois números naturais.

Sequência de Fibonacii

Examine a sequência de números a seguir, conhecida como Sequência de Fibonacii:

0 1 1 2 3 5 8 13 21 34 55 ...

Cada número da sequência é a soma dos dois números anteriores:

0 + 1 = 1
1 + 1 = 2
1 + 2 = 3
2 + 3 = 5
3 + 5 = 8 
...

Se fizermos

fib(0) = 0
fib(1) = 1

podemos definir a sequência de Fibonacci de maneira recursiva como:

fib(n) = n se n = 0 ou n = 1
fib(n) = fib(n - 2) + fib(n - 1) se n >= 2

Excercício

Implemente uma função recursiva para implementar uma sequência de Fibonacci para um dado inteiro n.

Torres de Hanoy

Pesquisa e exercício

1. Faça uma pesquisa sobre o problema conhecido como Torres de Hanoy;
2. Pesquise e implemente um programa que resolva o problema das Torres de Hanoy, utilizando funções recursivas.

Número mínimo de movimentos

Função matemática

Solução interativa X Solução recursiva

Wikipédia: Torres de Hanoy

#include <stdio.h>
#include <stdlib.h>

void solve(int QTD_DISCOS, char origem, char destino, char temp) {
  static int rank = 0;

  if (QTD_DISCOS > 0) {
    solve(QTD_DISCOS-1, origem, temp, destino);
    printf("%4d ) %c --> %c\n", ++rank, origem, destino);
    solve(QTD_DISCOS-1, temp, destino, origem);
  }
}

void main() {

  int nr;
  printf("Digite o numero de discos: ");
  scanf("%d", &nr);

  solve(nr, 'A', 'C', 'B');
}

Referências

---

--Evandro.cantu (discussão) 17h44min de 22 de outubro de 2014 (BRST)

---