Recursão em C
A maioria dos problemas em computação envolve a repetição de passos. Isso pode ser feito usando duas abordagens diferentes:
- Iterativa (
forewhile) - Recursividade
As soluções implementadas com recursivamente consiste em dividir o problema em partes menores de forma repetida até que o subproblema possa ser resolvido diretamente.
| Função Não-recursiva | Função Recursiva |
|---|---|
 |  |
Uma função recursiva é definida como uma função que chama a si mesma durante sua execução. Isso é feito de forma condicional, o que significa que a função decide se deve chamar a si mesma com base em uma condição, denotado de condição de parada ou caso base.
Uma função recursiva consiste em dois componentes essenciais:
- Definição da função: Esta é a definição principal da função que especifica o que a função faz. Pode incluir cálculos, operações e lógica. Essa definição também incluirá a condição sob a qual a função decidirá chamar a si mesma.
- Instâncias de execução: Quando a função é chamada durante a execução do programa, ela cria uma instância de execução. Essa instância executa as instruções definidas na função. No contexto da recursão, uma função pode chamar outra instância de execução da mesma função, ou seja, ela pode chamar a si mesma.
Note
Cada instância de execução atual da função A gerará uma nova instância de execução função A.
A execução de uma série de instâncias de uma função recursiva é semelhante à execução de uma série de instâncias não recursivas, com a diferença de que todas as instâncias são clones idênticos uma da outra. Cada instância da função é uma cópia exata da função original, e a chamada recursiva ocorre no mesmo ponto em todas elas. Portanto, todas as instâncias são executadas da mesma forma, mas em contextos separados.
No entanto, para que uma função recursiva funcione corretamente, ela deve incluir uma chamada de instância de execução que permita resolver o problema de forma direta, sem recorrer a chamadas adicionais a si mesma. Essa chamada de instância é o que chamamos de “condição de parada” ou “caso base”. Sem essa condição, a função continuaria chamando a si mesma indefinidamente, o que resultaria em um estouro de pilha (stack overflow).
O estouro de pilha é um problema sério que ocorre quando a função é chamada repetidamente sem uma maneira de parar. Isso pode levar a problemas na memória do computador e até mesmo ao término indesejado do programa. Portanto, é fundamental que toda função recursiva inclua uma condição de parada para garantir que a recursão termine em algum ponto. Isso é essencial para evitar um estouro de pilha e para que a função funcione corretamente.