Recursividade
Alunos: Yasmin Vier Scotti, Gustavo Vieira do
Nascimento, Pedro Cavalheiro Neto e Abel Felipe
Zwierzykowski, Alessandro Zientara.
O que é Recursividade é quando uma função
recursividad chama a si mesma para resolver um
problema. Ela divide o problema em
e? partes menores até chegar a um caso
base, que é a condição mais simples
em que a função para de se chamar e
retorna um resultado diretamente,
evitando um loop infinito.
CASO BASE
O caso base é a condição que
interrompe a recursão, evitando
chamadas infinitas. Ele fornece
uma resposta simples e direta ao
problema, permitindo que a
função retorne um valor sem mais
chamadas recursivas.
CHAMADAS RECURSIVAS
Cada chamada recursiva cria uma
if(number == 1){
nova instância da função na pilha de
return 1;
chamadas, com seu próprio conjunto }
de variáveis. Essas instâncias
trabalham independentemente até
que um caso base seja atingido,
permitindo o retorno dos resultados.
DIVISÃO DO PROBLEMA
A recursividade facilita a divisão
de problemas complexos em
partes menores e mais
gerenciáveis. Cada chamada
trata de um subconjunto do
problema, simplificando a
solução até que todas as partes
sejam resolvidas.
VANTAGENS DA RECURSIVIDADE
A recursividade pode resultar em
um código mais limpo e fácil de
entender, especialmente para
problemas que são naturalmente
recursivos. Muitas vezes, permite
escrever menos código do que com
iterações
DESVANTAGENS DA
RECURSIVIDADE
Chamadas recursivas podem ser
menos eficientes em termos de
tempo e memória, consumindo
espaço na pilha e levando a um
erro de "estouro de pilha".
Também pode ser mais difícil de
entender depois.
Exemplos de
recursividade:
● Fatorial
● Sequência de Fibonacci
● Busca Binária
● Inversão de String
● Cálculo de Potência
FATORIAL
O fatorial de um número n (denotado como n!) é o produto de todos os
números inteiros positivos de 1 a n. O caso base é que o fatorial de 0 e
1 é 1.
function fatorial(n) {
if (n === 0 || n === 1) {
return 1;
}
return n * fatorial(n - 1);
}
Sequência de
Fibonacci
A sequência de Fibonacci é uma série de números em que cada número é a soma dos
dois anteriores, começando por 0 e 1. O caso base é fibonacci(0) = 0 e fibonacci(1) = 1.
function fibonacci(n) {
if (n === 0) {
return 0;
}
if (n === 1) {
return 1;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}
BUSCA BINÁRIA
A busca binária é um algoritmo eficiente para encontrar um elemento em uma lista
ordenada. Ele divide a lista em metades e continua a busca na metade relevante até
encontrar o elemento ou esgotar a lista.
function buscaBinaria(arr, alvo, esquerda, direita) {
if (esquerda > direita) {
return -1;
}
const meio = [Link]((esquerda + direita) / 2);
if (arr[meio] === alvo) {
return meio;
} else if (arr[meio] < alvo) {
return buscaBinaria(arr, alvo, meio + 1, direita);
} else {
return buscaBinaria(arr, alvo, esquerda, meio - 1);
}
}
Inversão de
String
A inversão de uma string usando recursividade envolve pegar o último caractere da
string e adicioná-lo na frente do que sobrou da string (menos esse último caractere).
Continuamos esse processo até que a string se torne vazia, que é o caso base .
function inverterString(str) {
if ([Link] === 0) {
return "";
}
return [Link]([Link] - 1) + inverterString([Link](0, -1));
}
Cálculo de
Potência
O cálculo de potência recursivo determina o resultado de um número (base) elevado a
um expoente (expoente). A lógica recursiva baseia-se em multiplicar a base por ela
mesma até que o expoente se torne 0, que é o caso base .
function potencia(base, expoente) {
if (expoente === 0) {
return 1;
}
return base * potencia(base, expoente - 1);
}
AGRADESÇEMOS A
ATENÇÃO!