Exemplo de código usando recursividade em C
Definição formal[editar | editar código-fonte]
Na matemática e na ciência da computação, a recursão especifica (ou constrói) uma classe de objetos ou métodos (ou um objeto de uma certa classe) definindo alguns poucos casos base ou métodos muito simples (freqüentemente apenas um), e então definindo regras para formular casos complexos em termos de casos mais simples.
Por exemplo, segue uma definição recursiva da ancestralidade de uma pessoa:
Os pais de uma pessoa são seus antepassados (caso base);
Os pais de qualquer antepassado são também antepassados da pessoa em consideração (passo recursivo).
É conveniente pensar que uma definição recursiva define objetos em termos de objetos “previamente definidos” dessa mesma classe que está sendo definida.
Definições como esta são frequentemente encontradas na matemática, por exemplo, a definição formal dos números naturais diz que 0 (zero) é um número natural, e todo número natural tem um sucessor, que é também um número natural.
Recursão em ciência da computação[editar | editar código-fonte]
Ver artigo principal: Recursividade (Ciência da Computação)
Um método comum de simplificação é dividir o problema em subproblemas do mesmo tipo. Como técnica de programação, este método é conhecido como dividir e conquistar e é a chave para a construção de muitos algoritmos importantes, bem como uma parte fundamental da programação dinâmica.
A recursão na programação é bem exemplificada quando uma função é definida em termos de si mesma. Um exemplo da aplicação da recursão são os parsers (analisadores gramaticais) para linguagens de programação. Uma grande vantagem da recursão é que um conjunto infinito de sentenças possíveis, designs ou outros dados podem