Bacharelando em Computação

1.1 Definio Um objeto dito recursivo se ele consistir parcialmente ou for definido em termos de si prprio. Recurses ocorrem na matemtica, informtica, no dia a dia... Exemplos de recurso em definies matemticas Nmeros naturais 0 um nmero natural O sucessor de um nmero natural um nmero natural Funo Fatorial (n) para inteiros positivos 0 1 n0 n n (n - 1) 1.2 Algoritmos Recursivos Um algoritmo que para resolver um problema divide-o em subproblemas mais simples, cujas solues requerem a aplicao dele mesmo, chamado recursivo. Em programao, uma subrotina (procedimento ou funo) recursiva quando ela chama a si mesma. Suponha uma rotina recursiva R formada por um conjunto de comandos C (que no contm chamadas a R) e uma chamada (recursiva) R 1.3 Tipos de Recurso Recurso Direta quando em uma subrotina existe uma chamada para a prpria subrotina, independentemente dos valores dos parmetros Recurso Indireta As subrotinas so conectadas atravs de uma cadeia de chamadas sucessivas que acaba retornando primeira que a desencadeou 1.4 Funcionamento da Recurso A subrotina permite que seja dado um nome a um conjunto de comandos. Um desses comandos pode ser a chamada prpria subrotina. As subrotinas possuem objetos locais sem significado fora dela (variveis, parmetros, constantes, tipos e subrotinas). Toda vez que tal subrotina for executada recursivamente, um novo conjunto de variveis locais e parmetros so criados. Ainda que variveis e parmetros tenham o mesmo nome os identificadores se referem ao conjunto criado mais recentemente (seus valores so diferentes). Como ocorre nos comandos repetitivos, as chamadas recursivas possibilitam a no terminao (looping). Para tal, deve ser condicionado uma expresso lgica que, em algum instante, tornar-se- false e permitir que a recurso termine Um teste define, a cada momento, se o problema ter soluo trivial ou geral. Em termos matemticos, a recurso uma tcnica que, atravs de substituies sucessivas, reduz o