Duvida sobre o funcionamento da recursividade

Oi Rafael, tudo bem?

A recursividade é caracterizada por ser uma função que chama a si mesma, certo ? E este comportamento que citou, da variável armazenar o valor quando chama a si própria, ocorre somente nas funções recursivas porque elas trabalham com uma espécie de pilha de chamadas na memória. Então imagine que a variável qtd inicialmente seja 5. Então ela vai empilhando na memória e retorna o último valor de acordo com a operação feita(qtd-1) até chegar no caso base.

5

4

3

2

1

0

Quando chega no 0, ela chega em sua condição de parada(caso base) e sai da função recursiva. Por isto que funções recursivas são caracterizadas por consumir muita memória, fato no qual leva a muitos programadores evitarem seu uso em aplicações grandes, por exemplo. Mas vale ressaltar o seu uso em casos que a solução recursiva seja mais simples do que a versão iterativa ou em casos que a linguagem ofereça algum tipo de suporte para sobrecarga de memória.

Qualquer dúvida estou a disposição. Espero ter ajudado. Bons estudos!!!

Tradicionalmente, funções recebem argumentos de acordo com duas estratégias distintas: por valor ou por referência. Cada linguagem adota uma destas como padrão --- e.g. C adota a passagem por valor. Isso significa que em C uma chamada a uma função cria uma cópia na pilha dos valores de entrada, e são essas cópias que são alteradas pela função. O argumento da função, portanto, é uma variável implícita, à qual o valor passado é atribuído. Por este motivo, uma chamada a uma função não causa side-effects nos argumentos passados --- i.e. o valor das variáveis passadas à função não se alteram após o retorno da função. Evidentemente C fornece uma forma de emular chamadas por referência quando se usam ponteiros, e neste caso temos sim side-effects. Mas essa é outra história.

#include <stdio.h>
#include <stdint.h>

uint64_t tailrec_fat(uint64_t x, uint64_t acc) {
  return (x == 0) ? acc : tail_fat(x - 1, x * acc);
}

#define FAT(x) tailrec_fat(x, 1)

int main(int argc, char *argv[]) {
  uint64_t x = 3;

  printf("%llu! = %llu\n", x, FAT(x));
}

Acima, temos uma implementação da função fatorial. O domínio da função tailrec_fat aceita valores em [0, infinito), e portanto não importa o quão grande for a cadeia de chamadas, a mesma sempre irá convergir para o caso base, pois a cada nova chamada ela se aproxima do ponto de fuga. E essa é a condição fundamental de qualquer problema recursivo.

Recursividade é um conceito fundamental na matemática e ciência da computação, mas em se tratando de programação, temos de tomar cuidado com seu uso, pois se não forem feitas adequadamente, tornam-se um grande problema de performance. A cada chamada cria-se uma nova pilha e muda-se o contexto, e isso pode levar a um estouro de pilha.

Problemas de natureza logarítmica, como a busca binária, são ótimos candidatos para o uso de recursão, que provê soluções sucintas e elegantes. Problemas de ordem linear ou superior não costumam ser bons candidatos, a menos que se faça uso de otimizações. O exemplo acima é linear, mas foi codificado de um modo que compilador possa eliminar as chamadas recursivas, e substitui-las por um laço. Para mais informações, busque por tail call elimination.

P.S.: O programa acima é compatível como o padrão C99, ou superior. Costumo escrever código usando o padrão mais novo, no momento C17. No GCC, use as flags -O3 -std=c17 para conseguir as otimizações de eliminação recursiva.