Explicando a Recursividade

Um algoritmo é recursivo quando ele usa a si mesmo, más com parâmetros diferentes, para computar um problema. Pode ser uma função/método (subprogramação).

É uma técnica extremamente utilizada em aplicações matemáticas, onde são escalonada funções até que se obtenha o resultado final. (Algo como resolver uma equação “de trás para frente”)

É importante que ao usar uma função recursivamente, a mesma tenha um ponto de finalização, ou seja, um dos retornos da função que não dependa mais da recursão.

Um exemplo clássico é o cálculo do fatorial de um número, ex: 5! = 5 * 4 * 3 * 2 * 1 = 120. Acompanhe o algoritmo abaixo:

#include <conio.h>
#include <stdio.h>

int CalcularFatorial(int numero)
{
    // -> Fórmula numero! = numero*(numero-1)!

    // -> Condição de término.
    if(numero == 1)
        return 1;
    else if(numero == 0)
        return 1;

    // -> Chamada recursiva.
    int resultado = numero * CalcularFatorial(numero - 1);

    return resultado;
}

void main()
{
    int numero = 0;
    int resultado = 0;
    printf("Informe um número para o cálculo Fatorial: ");
    scanf("%d", &numero);

    // -> Chama a função pela primeira vez.
    resultado = CalcularFatorial(numero);

    printf("Resultado: %d", resultado);
    getch();
}

 

Este código apresenta a seguinte saída:

Na execução do cálculo houve um empilhamento de chamadas da função CalcularFatorial(), até que a mesma atingisse a condição de saída, ou seja numero == 1 ou numero == 2. Acompanhe este processo nas imagens abaixo:

Podemos explorar a recursividade em diversos aspectos, tomando sempre o cuidado coma sua condição de saída. Acompanhe mais um exemplo, agora com o cálculo de uma seqüência Fibonacci:

#include <stdio.h>
#include <conio.h>

int CalcularFibonacci(int numero)
{
    // -> Fórmula: F(n) = F(n-1) + F(n-2)

    // -> Condição de Saída
    if (numero == 0)
        return 0;
    else if (numero == 1)
        return 1;

    // -> Chamada Recursiva.
    int resultado = CalcularFibonacci(numero - 1) + CalcularFibonacci(numero - 2);
    return resultado;
}

void main()
{
    int numero = 0;
    printf("Informe um número para o cálculo Fibonacci: ");
    scanf("%d", &numero);

    // -> Chamada da função pela primeira vez.
    int resultado = CalcularFibonacci(numero);

    printf("Resultado: %d", resultado);
    getch();
}

 

Este código gera a seguinte saída:

 

É isso daí, agora ficam alguns exercícios para refletirmos:

1. Fazer um programa em C que some os números inteiros positivos de 1 a n.
2. Fazer um programa em C que calcule o resultado de um número inteiro elevado a um segundo número inteiro, ambos positivos. Ex:  2³.
3. 

Espero ter ajudado, até a próxima :)