Recursão
Recursão é uma técnica de programação importante que faz com que uma função para chamar a mesmo. Um exemplo é o cálculo de fatoriais. O fatorial de 0 é definido especificamente para ser 1. O fatorial de n, um inteiro maior que 0, é o produto de todos os inteiros no intervalo de 1 a n.
Usando recursão
O parágrafo seguinte é uma função definida em palavras, que calcula um fatorial.
"Se o número for menor que zero, rejeitá-lo. Se não for um número inteiro, rejeitá-lo. Se o número for zero, o fatorial é um. Se o número for maior que zero, multiplique-o pelo fatorial do número seguinte menor."
Para calcular o fatorial de qualquer número maior que zero, você deve calcular o fatorial de pelo menos um outro número. A função deve chamar a próprio para o próximo número menor antes que ele pode executar o número atual. Este é um exemplo de recursão.
Recursão e iteração (loop) estão fortemente relacionadas — uma função pode retornar os mesmos resultados com recursão ou iteração. Geralmente uma determinada computação será justificando uma técnica ou outro e, em seguida, basta você escolhe a abordagem mais natural ou preferível.
Apesar da utilidade de recursão, você pode criar facilmente uma função recursiva que nunca retorna um resultado e não puder alcançar um ponto de extremidade. Tal recursão faz com que o computador executar um infinito loop. Aqui está um exemplo: omitir a primeira regra (aquele sobre números negativos) a partir da descrição textual de calcular um fatorial e tentar calcular o fatorial de qualquer número negativo. Esse procedimento falhar porque para calcular o fatorial de, por exemplo, -24, você deve calcular o fatorial de -25. Para calcular o fatorial de -25, primeiro você deve calcular o fatorial de-26 e assim por diante. Obviamente, isso nunca atinge uma conclusão.
Outro problema que pode ocorrer com a recursão é que uma função recursiva pode usar todos os recursos disponíveis (como o espaço de memória e a pilha do sistema). Cada vez que um recursiva chamadas de função propriamente dito (ou chamar outra função que chama a função original), ele usa alguns recursos. Esses recursos são liberados quando sai de função recursiva, mas uma função que tem muitos níveis de recursão pode usar todos os recursos disponíveis. Quando isso acontece, uma exceção é lançada.
Portanto, é importante para o design recursivas: funções com cuidado. Se você suspeitar de qualquer chance de uma recursão excessiva (ou infinita), crie a função para contar o número de vezes que chama a mesmo e definir um limite no número de chamadas. Se a função chama a mesmo mais vezes que o limite, a função pode encerrar automaticamente. O número ideal de máximo de iterações depende da função recursiva.
Eis a função fatorial novamente, desta vez escrita em código de JScript. Anotação de tipo é usada para a função aceita apenas números inteiros. Se um número inválido for passado (isto é, um número menor que zero), a instrução throw gera um erro. Caso contrário, uma função recursiva é usada para calcular o fatorial. A função recursiva leva dois argumentos, um para o argumento fatorial e outra para o contador que controla o nível atual de recursão. Se o contador não alcançar o nível máximo de recursão, o fatorial do número original é retornado.
function factorialWork(aNumber : int, recursNumber : int ) : double {
// recursNumber keeps track of the number of iterations so far.
if (aNumber == 0) { // If the number is 0, its factorial is 1.
return 1.;
} else {
if(recursNumber > 100) {
throw("Too many levels of recursion.");
} else { // Otherwise, recurse again.
return (aNumber * factorialWork(aNumber - 1, recursNumber + 1));
}
}
}
function factorial(aNumber : int) : double {
// Use type annotation to only accept numbers coercible to integers.
// double is used for the return type to allow very large numbers to be returned.
if(aNumber < 0) {
throw("Cannot take the factorial of a negative number.");
} else { // Call the recursive function.
return factorialWork(aNumber, 0);
}
}
// Call the factorial function for two values.
print(factorial(5));
print(factorial(80));
A saída deste programa é:
120
7.156945704626378e+118