As funções recursivas são uma classe especial de funções que tendem a utilizar a sua própria produção nos seus cálculos. Uma função recursiva é aquela que se chama a si própria repetidamente até que uma determinada condição seja satisfeita. O ponto-chave a lembrar é que o mesmo código é executado várias vezes até que o resultado desejado seja obtido.
Recursion é uma técnica de programação informática em que uma determinada linha de código é executada repetidamente por uma função até que uma determinada condição seja satisfeita. É um tipo de iteração, mas com uma torção. A função chama-se a si mesma para executar a mesma linha de código várias vezes, de modo a alcançar o resultado desejado.
A função começa por verificar a condição associada à função recursiva. Se a condição for verdadeira, a função chama-se a si própria para executar a mesma linha de código várias vezes. Este processo continua até ser obtido o resultado desejado.
A utilização de funções recursivas pode ser muito benéfica. Pode poupar tempo aos programadores ao não ter de escrever um mecanismo de looping separado para alcançar o resultado desejado. Pode também ajudar a reduzir a complexidade do código, o que pode ajudar a facilitar a depuração e a manutenção.
Infelizmente, existem algumas desvantagens potenciais na utilização de funções recursivas. Pode ser difícil de depurar e manter se o código não estiver devidamente escrito. Além disso, as funções recursivas podem ocupar mais espaço de memória e causar problemas de desempenho.
As funções recursivas são melhor utilizadas quando se trata de problemas que podem ser decompostos em problemas mais pequenos e semelhantes. Isto é porque o mesmo código pode ser usado para resolver o problema. Além disso, as funções recursivas podem ser usadas para simplificar tarefas complexas e quando se lida com estruturas de dados tais como árvores e gráficos.
Algumas das utilizações mais comuns de funções recursivas incluem a resolução de problemas matemáticos tais como números factoriais e Fibonacci, atravessar árvores e gráficos, e algoritmos de ordenação tais como quicksort e mergesort.
As funções recursivas são uma ferramenta incrivelmente poderosa que pode ser usada para resolver muitos tipos diferentes de problemas. Embora possa ser difícil de depurar e manter, pode ser uma grande poupança de tempo para os programadores e pode simplificar tarefas complexas. Saber quando e como utilizar funções recursivas é uma habilidade importante para qualquer programador.
Há duas partes principais para escrever uma função recursiva: o caso base e o caso recursivo. O caso base é o input mais simples possível que deseja que a sua função lide, e o caso recursivo é o que deseja que a sua função faça para todos os outros inputs.
Por exemplo, digamos que quer escrever uma função que aceita um número e imprime a sequência de Fibonacci até esse número. A caixa de base seria se a entrada fosse 0 ou 1, caso em que a função imprimiria apenas 0 ou 1. Para todas as outras entradas, o caso recursivo seria imprimir a sequência de Fibonacci até esse número.
Para o fazer, seria necessário primeiro descobrir qual é a sequência de Fibonacci. A sequência de Fibonacci é uma série de números em que cada número é a soma dos dois números anteriores. Assim, a sequência vai de 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, e assim por diante.
Quando souber qual é a sequência de Fibonacci, pode escrever uma função que aceita um número e imprime a sequência até àquele número. Por exemplo, se a entrada for 5, a função imprimirá 0, 1, 1, 2, 3, 5.
Aqui está o pseudo-código para tal função:
função imprimirFibonacci(num) {
// caixa base
se (num == 0 || num == 1) {
imprimir num;
}
// caso recursivo
outro {
printFibonacci(num - 1);
printFibonacci(num - 2);
}
}
Uma fórmula recursiva é uma fórmula que define uma sequência em termos de si mesma. Especificamente, é uma fórmula em que cada termo sucessivo é definido como uma função do termo anterior. Por exemplo, a sequência de Fibonacci pode ser definida recursivamente da seguinte forma: a1 = 1, a2 = 1, e an = a(n-1) + a(n-2) para n > 2.
As funções recursivas são utilizadas na programação de computadores porque permitem aos programadores definir uma função em termos próprios. Isto significa que a função pode chamar-se a si própria durante a sua execução, o que pode ser útil para executar tarefas que precisam de ser repetidas várias vezes.
Existem três propriedades básicas que uma função recursiva deve ter:
1. um caso base: esta é a entrada mais simples possível para a função, e deve ter uma saída conhecida. Por exemplo, o caso base para uma função que calcula o factorial de um número poderia ser quando a entrada é 1, e a saída é 1.
2. Um caso recursivo: isto é quando a função se chama a si própria com uma entrada ligeiramente mais simples do que a original. Por exemplo, o caso recursivo para a função factorial poderia ser quando a entrada é n-1, e a saída é n * (n-1)!
3. uma condição terminal: isto é o que diz à função quando parar de se repetir e devolver a resposta final. Por exemplo, a condição terminal para a função factorial poderia ser quando a entrada é inferior ou igual a 1.