Vamos examinar um exemplo coloquial de procedimento recursivo. Imaginemos ter que encontrar no dicionário o significado da palavra "jururu". É claro que ninguém vai ler sequencialmente o dicionário até chegar à palavra procurada.
Vamos definir o processo de achar uma palavra num dicionário em termos algorítmicos mais ou menos livres procura-palavra (Dicionário, palavra-procurada):
abrir o dicionário nas palavras que iniciam com a letra “j”
ler sequencialmente duas páginasse palavra procurada estiver nas páginasfim da leitura sequencial
fim da procura
se palavra procurada não estiver nas páginasprocura palavra nas próximas páginasfim se
se palavra-procurada for encontradaimprimir a sua definição fim do algoritmofim se
se palavra-não for encontradaimprimir ("palavra procurada não existe")fim do algoritmofim se
fim
O algoritmo é recursivo no sentido de que ele chama a ele mesmo. Note que ocorre a procura da palavra várias vezes até encontrá-la, ou, caso depois da procura não se encontre o que deseja, ele encerra o algoritmo. Nesse caso, o processo é finito, já que, a cada chamada, o universo de pesquisa é menor. Na primeira vez, ele é todo o dicionário, na segunda vez, apenas a metade, na terceira vez, uma quarta parte e assim por diante. Finalmente, há uma condição que estabelece o fim da pesquisa.
No exemplo do dicionário, vimos às três características que um problema recursivo tem que ter: