DC-UFRPE/Bacharelado em Ciência da Computação/Introdução a Programação I/Função Recursiva

Uma função recursiva é uma função que chama a si mesma repetidamente, até que uma condição de parada seja atingida. Ou seja, a função é definida em termos dela mesma, permitindo que problemas complexos sejam decompostos em subproblemas menores e mais simples.

Em todas as funções recursivas existe:

• Um passo básico (ou mais) cujo resultado é imediatamente conhecido.

• Um passo recursivo em que se tenta resolver um subproblema do problema inicial.

Essa técnica é amplamente utilizada em programação, especialmente para problemas matemáticos e algoritmos. Um exemplo comum de uma função recursiva é a função de Fibonacci, que é definida por:

int fibonacci(int n) {
    if (n <= 1) {
        return n;
    } else {
        return fibonacci(n-1) + fibonacci(n-2);
    }
}

Essa função retorna o n-ésimo número da sequência de Fibonacci, que é definida como a soma dos dois números anteriores. A condição de parada é quando n é menor ou igual a 1.

Para ilustrar como essa função é recursiva, vamos considerar a chamada fib(5). A função verifica que n é maior do que 1, então chama fib(4) e fib(3). A chamada fib(4) chama fib(3) e fib(2), enquanto a chamada fib(3) chama fib(2) e fib(1). Quando a chamada fib(1) é feita, a condição de parada é atingida e a função retorna 1. As outras chamadas são concluídas em seguida, resultando no valor de retorno da função original, que é 5.

Logo, ao utilizar uma função recursiva, devemos ter em mente o caso base(o estado mais simples da função) e a partir dele, montar a função que chama a si mesma.