Um procedimento recursivo contém, em sua descrição, uma ou mais chamadas a si mesmo, e deve possuir pelo menos uma chamada externa proveniente de um local exterior a ele. A um procedimento recursivo, tipicamente corresponde um não-recursivo que executa a mesma computação.