recursão

Alguns linguistas procuram descrever a sintaxe de línguas humanas (como o português, por exemplo) em termos computacionais. A recursão, neste caso, é utilizada como conceito teórico para descrever, entre outras coisas, sentenças ou sintagmas encaixados nas línguas naturais e artificiais (ver encaixamento). Assim, a recursão é definida como a propriedade matemática das expressões que são definidas em termos delas mesmas.

Por exemplo, na função x=xb, o termo x é definido em termos de si mesmo. Em um procedimento computacional, que funciona passo a passo, isto significa que o valor atribuído à variável x no passo 2 dependerá do valor atribuído a ela no passo 1. O valor atribuído no passo 3, por sua vez, dependerá do valor no passo 2. E assim por diante, até o procedimento ser interrompido por um valor estipulado pelo programa. Este recurso é usado para subdividir a resolução de um problema computacional em problemas menores utilizando uma mesma expressão, o que torna o programa muito mais enxuto e eficiente.