Recursividade em C

Uma função recursiva é uma função que chama ela mesma durante a sua execução.

• Função recursiva direta: chama ela mesma dentro da própria função;
• Função recursiva indireta: chama a si mesmo por meio de outra função;

O melhor exemplo de recursividade é através do cálculo de fatorial e essa operação é representada pelo símbolo de “!” . Para encontrar o fatorial de um número utilizamos a fórmula a seguir:

n! = n* (n-1) * (n-2) * … * 1

Obs: 1! e 0! (Fatorial de 1 e de 0) são iguais a 1.

Assim, vamos calcular o fatorial de 5. Exemplo: 5! = 5 * 4 * 3 * 2 * 1 = 120.

Note que o fatorial é uma sequência de operações semelhantes, multiplicações cada vez mais básicas até chegar em 1 (a sequência sempre é finalizada em 1).

Segue abaixo um código com uma função recursiva que calcula o fatorial de um número inteiro em C:

Outro exemplo de caso que envolve uma sequência de operações semelhantes é a série de Fibonacci. Portanto, podemos solucioná-la utilizando recursão.

A série de Fibonacci inicia com 0 e 1 e cada número subsequente é a soma dos dois números anteriores a ele. É uma série que acontece na natureza e descreve uma forma de espiral. Segue o exemplo abaixo:

Sequência de Fibonacci = 0, 1, 1, 2, 3, 5, 8, 13, 21, 34…

Obs: Pense nessa sequência como se fosse um vetor, ou seja, começando sempre pelo índice 0. Por exemplo: o Fibonacci (3) é o 2, o Fibonacci (4) é o 3 e assim em diante.

É importante notar que o Fibonacci(0) sempre será igual a 0 e o Fibonacci(1) sempre será igual a 1. Uma vez que, a sequência sempre começa por 0 e 1:

• Fibonacci(0) = A soma dos dois números anteriores ele é 0, visto que não há números antes do 0. Portanto, Fibonacci(0) = 0 + 0 = 0;
• Fibonacci(1) = A soma dos dois números anteriores é 1, visto que temos 0 e 1 como antecedentes. Portanto, Fibonacci(1) = 0 + 1 = 1;

A seguir, segue a fórmula para o cálculo de Fibonacci dos números diferentes de 0 e 1:

Fibonacci(n) = Fibonacci(n - 1) + Fibonacci(n - 2 )

Segue abaixo, o exemplo de código que calcula o FIbonacci de um número em C:

Por último, temos um exemplo de como somar todos os valores de um vetor de inteiros através de uma função recursiva.

Para compreender melhor o exemplo abaixo, pense em um vetor de 3 números, de tamanho 2.

• Linha 3 ->” int soma(int v[], int tam)” = É passado como parâmetro pra função soma o vetor = {1,2,3} e o tamanho 3. Obs: estamos diminuindo um elemento para o tamanho real na linha 7, o tamanho real do vetor é 2, visto que começa com o indice 0.
• Linha 4 e 5 -> “if(tam == 0){return 0;}” = Se o vetor tiver 0 elementos, a soma retornará 0.
• Linha 6 -> “else{ return v[tam — 1] + soma(v, tam — 1);}” = Se não, retorne a posição do vetor equivalente a v[tam -1], no nosso caso seria v[3 -1] = v[2] = 3. Apenas para melhor compreensão guarde esse valor 3 em sua memória.
• Linha 6 -> soma(v, tam — 1); = É chamada a função soma de forma recursiva, passando o vetor inteiro, isto é, v{1,2,3} e tam-1 para a função.
• Linha 6 -> “else{ return v[tam — 1] + soma(v, tam — 1);} ”Entra novamente no se não e agora o tam é 2, portanto v[tam -1] = v[2–1] = v[1] = 2. Portanto vamos somar esse valor com o valor guardado em sua memória anteriormente. 3 + 2 = 5.
• Assim, esse loop se repetirá novamente até que seja efetuado 3 + 2 + 1 = 6, isto é, a soma de todos os valores do vetor. Repare que ele está somando esses elementos de trás para frente. A função funcionará da mesma forma com um vetor de n elementos.

Tente pensar em como a função acontece de forma simultânea para que assim, armazene os devidos valores e chegue no resultado final.

Referências

Canal Bóson Treinamentos, Lógica de Programação - Recursividade - 30. https://www.youtube.com/watch?v=M7c-m2xN9FQ

Programiz, C Recursion -https://www.programiz.com/c-programming/c-recursion

Canal Programe seu futuro, Curso de Programação C | Como somar os elementos de um vetor com recursão? | Aula 161 -https://www.youtube.com/watch?v=TgOQRIb_4CA