Funções recursivas

As linguagens de programação costumam oferecer suporte para a chamada de uma função dentro do bloco de código dela mesma. Essa chamada é dita recursiva. Abaixo um exemplo:

void recursividade() {
    recursividade();
}

A função de nome recursividade é chamada no corpo dela mesma. No entanto, essa chamada recursiva gera um loop infinito. Isto é, leva o programa a travar. Por isso, normalmente, as funções recursivas têm uma condição de parada para evitar o loop infinito. Veja o exemplo abaixo:


int fatorial( int n ) {
    if ( n == 0 )
        return 1;
    return n * fatorial( n-1 );
}

A função acima recebe como parâmetro um número e retorna o fatorial dele. Ex: fatorial de 3 = 3*2*1. Ou seja, fatorial de 3 é igual ao 3 vezes o fatorial de 2. Isso significa que o fatorial de N é igual a N vezes o fatorial de N-1. Atenção a condição de parada ( n == 0 ) que evida o loop infinito! Perceba que n vai sendo decrementado a cada chamada recursiva da função fatorial: fatorial( n-1 ) até atingir a condição de parada, quando a função é chamada com n igual a zero, é retornado o valor 1 sem, novamente, chamar recursivamente a função fatorial, o que termina a execução da chamada atual da função.

Abaixo outro exemplo, função que retorna o elemento da série fibbonacci, de acordo com o indice do elemento passado como parâmetro. Ex: fibo( 5 ) = fibo( 4 ) + fibo( 3 ), ou seja, fibo( n ) = fibo( n-1 ) + fibo( n-2 ).


int fibo( int n ) {
    if ( n == 1 || n == 2 )     
        return 1;   
    return fibo( n-1 ) + fibo( n-2 );
}

Lembrando que a série fibbonacci é: 1 1 2 3 5 8 13 21...

fibo(1) = 1;
fibo(2) = 1;
fibo(3) = fibo(2) + fibo(1) = 2;
fibo(4) = fibo(3) + fibo(2) = 3;
fibo(5) = fibo(4) + fibo(3) = 5;
fibo(6) = fibo(5) + fibo(4) = 8;
...
fibo(N) = fibo(N-1) + fibo(N-2);

Abaixo um exemplo de função recursiva que imprime (em ordem decrescente) os números de 1 a um número passado como parâmetro:


int imp_ordem_decrescente( int n ) {
    if ( n > 0 ) {  
        printf( "%d ", n );
        imp_ordem_decrescente( n-1 );
    }
}

Abaixo o código fonte completo:


#include <stdio.h>

int fatorial( n ) {
    if ( n == 0 )
       return 1;
    return n * fatorial( n-1 );
}

int fibo( int n ) {
    if ( n == 1 || n == 2 )     
        return 1;   
    return fibo( n-1 ) + fibo( n-2 );
}

int imp_ordem_decrescente( int n ) {
    if ( n > 0 ) {  
        printf( "%d ", n );
        imp_ordem_decrescente( n-1 );
    }
}

int main() {
    int num, fat, fib;
    
    printf( "Informe um numero: " );
    scanf( "%d", &num );
    
    fat = fatorial( num );
    fib = fibo( num );
    
    printf( "\nFatorial(%d) = %d", num, fat );
    printf( "\nFibo(%d) = %d", num, fib );  
    
    printf( "\nOrdem decrescente: " );
    imp_ordem_decrescente( num );
    
    return 0;
}

Exercício

1) Faça uma função recursiva que imprima (em ordem crescente) os números de 1 a um número informado pelo usuário. Exemplo de saída:

Informe um número: 10
Ordem crescente: 1 2 3 4 5 6 7 8 9 10

Dica: A função deve fazer a chamada recursivamente antes de imprimir o número.

Próximo - structs

Italo Info

Exercício