Agora que já aprendemos a criar nossas funções e procedimentos, vamos aprender o conceito de recursividade: o que é uma função / procedimento recursivo?

Uma função recursiva é uma função que chama a si mesma. A princípio isso pode parecer um pouco estranho, mas com um pouco de prática você verá que a ideia não é tão estranha quanto parece de início.

Vamos a um exemplo pra ajudar na compreensão. Imagine que desejamos fazer um procedimento (sem retorno) para imprimir todos os números inteiros de 30 até 0. Isso pode ser feito facilmente com uma repetição do tipo para. Inclusive faço aqui um alerta. Para entender recursão você precisa ter entendido como funcionam as estruturas de repetição. Se você tem dúvidas sobre essas estruturas, volte e revise estas aulas.

Voltando ao nosso exemplo, ele pode ser facilmente resolvido com uma repetição decrescente, como apresenta o exemplo a seguir.

	// procedimento para imprimir os números de 30 até 0
	funcao imprimirDecrescente(){
		inteiro i
		para(i = 30; i >= 0; i--)
			escreva(i, ", ")
	}

Perceba que nossa repetição possui três pontos fundamentais para que ela funcione bem: o valor inicial (30); uma condição de parada (i >= 0); e o incremento, neste caso um incremento negativo ou um decremento de uma unidade.

Agora vamos escrever um procedimento recursivo para resolver o mesmo problema. A recursão também é um processo de repetição. Contudo, a repetição é produzida por meio das chamadas recursivas.

A primeira diferença é que no procedimento recursivo nós precisamos receber o valor inicial (30) como parâmetro. Em seguida precisamos descobrir nosso ponto de parada. Isso é extremamente importante. Como uma recursão também é uma repetição, se não identificarmos nosso ponto de parada corretamente, podemos ter um loop infinito, assim como nas estruturas de repetição para e enquanto. Para identificar nosso ponto de parada, podemos olhar para nosso procedimento anterior. Perceba que o para irá executar enquanto i for maior ou igual a zero. Este é nosso ponto de para, o zero.

Se o valor recebido por parâmetro for exatamente igual a zero, então imprimir zero na tela. Apenas isso.

Contudo, e se o valor recebido for diferente de zero? Nesta caso, imprimirmos o valor recebido e, em seguida, fazemos a chamada recursiva, ou seja, chamamos o mesmo procedimento, porém, enviamos o valor recebido menos 1, pois já imprimirmos o valor recebido.

Perceba que, para o nosso exemplo com 30, resolvemos uma pequena parte do problema, imprimimos o valor 30 e, na sequência, chamamos o mesmo procedimento, mas agora com o valor 29. Em algum momento esse valor chegará a zero e dará fim às chamadas recursivas.

	funcao imprimirRecursivo(inteiro x){
		se(x == 0)
			escreva(x)
		senao{
			escreva(x, ", ")
			imprimirRecursivo(x - 1)
		}
	}