Algoritmos recursivos mais comuns em JavaScript, Python e PHP
Partilhar
Após o artigo introdutório sobre programação recursiva, é hora de ver alguns exemplos práticos.
Abaixo você verá os exemplos mais comuns utilizados durante o treinamento de programação, codificados em JavaScript, Python e PHP.
Antes de passar aos códigos, deixamos uma curiosidade sobre PHP:
O nome “PHP” é uma sigla recursiva, o que é uma curiosidade interessante no mundo da computação. Originalmente, PHP significava “Personal Home Page”, pois foi criado em 1994 por Rasmus Lerdorf como um conjunto de ferramentas simples para rastrear visitas à sua página pessoal da web. Com o tempo, a linguagem evoluiu e adquiriu muito mais recursos, tornando-se uma linguagem de programação completa.
À medida que o PHP cresceu em complexidade e funcionalidade, seu nome foi alterado para “PHP: Hypertext Preprocessor”. É aqui que a recursão é encontrada: a sigla “PHP” inclui o mesmo “P” em “PHP”, o que cria um loop lógico. Ou seja, o significado da sigla PHP contém o próprio nome “PHP”, o que dá origem à recursão em seu nome.
Uma sigla recursiva é aquela em que uma das letras da sigla se refere à própria sigla. Esse tipo de sigla é uma espécie de “piada interna” que reflete o senso de humor e a engenhosidade dos programadores.
1. Fatorial de um número
O fatorial de um inteiro positivo n é o produto de todos os inteiros positivos de 1 a n. É denotado como n!
Python
def factorial(n):
if n == 0 or n == 1:
return 1
else:
return n * factorial(n - 1)
JavaScript
function factorial(n) {
if (n === 0 || n === 1) {
return 1;
} else {
return n * factorial(n - 1);
}
}
PHP
function factorial($n) {
if ($n == 0 || $n == 1) {
return 1;
} else {
return $n * factorial($n - 1);
}
}
2. Sequência de Fibonacci
A sequência de Fibonacci é uma sequência de números inteiros em que cada número é a soma dos dois anteriores. Normalmente começa com os números 0 e 1 e, a partir daí, cada termo sucessivo é calculado como a soma dos dois números anteriores na sequência.
Python
def fibonacci(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return fibonacci(n - 1) + fibonacci(n - 2)
JavaScript
function fibonacci(n) {
if (n === 0) {
return 0;
} else if (n === 1) {
return 1;
} else {
return fibonacci(n - 1) + fibonacci(n - 2);
}
}
PHP
function fibonacci($n) {
if ($n == 0) {
return 0;
} elseif ($n == 1) {
return 1;
} else {
return fibonacci($n - 1) + fibonacci($n - 2);
}
}
3. Pesquisa binária
Python
def binary_search(arr, target, low, high):
if low > high:
return -1
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] > target:
return binary_search(arr, target, low, mid - 1)
else:
return binary_search(arr, target, mid + 1, high)
JavaScript
function binarySearch(arr, target, low, high) {
if (low > high) {
return -1;
}
let mid = Math.floor((low + high) / 2);
if (arr[mid] === target) {
return mid;
} else if (arr[mid] > target) {
return binarySearch(arr, target, low, mid - 1);
} else {
return binarySearch(arr, target, mid + 1, high);
}
}
PHP
function binarySearch($arr, $target, $low, $high) {
if ($low > $high) {
return -1;
}
$mid = floor(($low + $high) / 2);
if ($arr[$mid] == $target) {
return $mid;
} elseif ($arr[$mid] > $target) {
return binarySearch($arr, $target, $low, $mid - 1);
} else {
return binarySearch($arr, $target, $mid + 1, $high);
}
}
4. Torres de Hanói
As Torres de Hanói é um problema clássico de recursão que consiste em mover n discos de tamanhos diferentes de um posto inicial para outro, utilizando um terceiro posto auxiliar e seguindo regras específicas. A solução baseia-se em dividir o problema em subproblemas menores, movendo primeiro os n-1 discos, depois o disco maior e, finalmente, os n-1 discos restantes, aplicando recursão em cada etapa.
Python
def hanoi(n, source, target, auxiliary):
if n == 1:
print(f"Mova disco 1 de {source} para {target}")
return
hanoi(n - 1, source, auxiliary, target)
print(f"Mova disco {n} de {source} para {target}")
hanoi(n - 1, auxiliary, target, source)
JavaScript
function hanoi(n, source, target, auxiliary) {
if (n === 1) {
console.log(`Mova disco 1 de ${source} para ${target}`);
return;
}
hanoi(n - 1, source, auxiliary, target);
console.log(`Mova disco ${n} de ${source} para ${target}`);
hanoi(n - 1, auxiliary, target, source);
}
PHP
function hanoi($n, $source, $target, $auxiliary) {
if ($n == 1) {
echo "Mova disco 1 de $source para $target\n";
return;
}
hanoi($n - 1, $source, $auxiliary, $target);
echo "Mova disco $n de $source para $target\n";
hanoi($n - 1, $auxiliary, $target, $source);
}
5. Imprima uma lista de trás para frente
Python
def print_reverse(arr):
if len(arr) == 0:
return
print(arr[-1])
print_reverse(arr[:-1])
JavaScript
function printReverse(arr) {
if (arr.length === 0) {
return;
}
console.log(arr[arr.length - 1]);
printReverse(arr.slice(0, -1));
}
PHP
function printReverse($arr) {
if (count($arr) == 0) {
return;
}
echo array_pop($arr) . "\n";
printReverse($arr);
}
6. Adicione os elementos de uma lista
Python
def sum_list(arr):
if len(arr) == 0:
return 0
else:
return arr[0] + sum_list(arr[1:])
JavaScript
function sumList(arr) {
if (arr.length === 0) {
return 0;
} else {
return arr[0] + sumList(arr.slice(1));
}
}
PHP
function sumList($arr) {
if (count($arr) == 0) {
return 0;
} else {
return array_shift($arr) + sumList($arr);
}
}
7. Permutações de uma string
Python
def permute(s, answer=''):
if len(s) == 0:
print(answer)
return
for i in range(len(s)):
ch = s[i]
left = s[:i]
right = s[i + 1:]
permute(left + right, answer + ch)
JavaScript
function permute(s, answer = '') {
if (s.length === 0) {
console.log(answer);
return;
}
for (let i = 0; i < s.length; i++) {
let ch = s[i];
let left = s.slice(0, i);
let right = s.slice(i + 1);
permute(left + right, answer + ch);
}
}
PHP
function permute($s, $answer = '') {
if (strlen($s) == 0) {
echo $answer . "\n";
return;
}
for ($i = 0; $i < strlen($s); $i++) {
$ch = $s[$i];
$left = substr($s, 0, $i);
$right = substr($s, $i + 1);
permute($left . $right, $answer . $ch);
}
}
Esperamos que tenham gostado e que não se esqueçam de nos seguir no LinkedIN, onde anunciamos cada novo artigo, e nas restantes redes sociais onde começaremos a carregar conteúdos sobre ciência mas diferentes.
https://www.linkedin.com/company/the-science-driven-company/
https://www.instagram.com/science.driven/
https://www.tiktok.com/@science.driven
https://www.youtube.com/@ScienceDriven
Perguntas frequentes sobre algoritmos recursivos em JavaScript, Python e PHP
Quais são os algoritmos recursivos mais comuns?
Os algoritmos recursivos mais comuns no ensino de programação são o fatorial, a sequência de Fibonacci, a busca binária, a Torre de Hanói, a soma e a inversão de listas e a geração de permutações. No dia a dia profissional aparecem o merge sort, o quicksort, a busca em profundidade em grafos e a leitura de estruturas aninhadas como JSON. Todos têm um caso base e um passo que reduz o problema.
Como fazer uma função recursiva em Python?
Para fazer uma função recursiva em Python, use def, crie um caso base que devolve um valor direto e chame a própria função com um argumento menor. O fatorial cabe em poucas linhas com "if n <= 1 return 1" e "return n * fatorial(n - 1)". Vale lembrar que o Python não otimiza a recursão de cauda e interrompe a execução depois de 1000 chamadas aninhadas por padrão.
Qual é o limite de recursão no Python?
O limite padrão de recursão no Python é de 1000 chamadas aninhadas. Acima disso, o interpretador lança RecursionError para evitar que o programa estoure a pilha do sistema. Dá para consultar o valor com sys.getrecursionlimit() e mudá-lo com sys.setrecursionlimit(), mas um limite alto demais pode derrubar o processo sem aviso. Para entradas muito profundas, o mais seguro é reescrever o algoritmo com um laço ou uma pilha explícita.
O que significa o erro "Maximum call stack size exceeded" no JavaScript?
Esse erro significa que uma cadeia de chamadas, quase sempre uma recursão sem caso base alcançável, encheu a pilha de chamadas. No Chrome e no Node.js ele aparece como RangeError. A profundidade máxima depende do motor e da memória disponível e costuma ficar entre milhares e dezenas de milhares de chamadas. A especificação ES2015 prevê chamadas de cauda otimizadas, mas na prática só o Safari as implementa.
O PHP tem limite de recursão?
O PHP não fixa um número máximo de chamadas recursivas como o Python faz. O teto real é dado pela memória e pelo tamanho da pilha do sistema. A partir do PHP 8.3, o motor percebe quando a pilha está quase cheia e lança um Error que pode ser tratado, evitando que o processo simplesmente caia. Ferramentas de depuração como o Xdebug acrescentam seu próprio limite de aninhamento, ajustável no php.ini.
O que significa a sigla PHP?
A sigla PHP significa "PHP: Hypertext Preprocessor", um acrônimo recursivo porque a própria sigla aparece dentro da definição. Rasmus Lerdorf começou o projeto em 1994 e o lançou em 1995 como Personal Home Page Tools. O nome recursivo chegou com o PHP 3, em 1998. É uma piada clássica entre programadores, no mesmo estilo de GNU, que quer dizer "GNU's Not Unix".
Quantos movimentos a Torre de Hanói exige?
A Torre de Hanói com n discos exige no mínimo 2^n − 1 movimentos. A solução recursiva leva n − 1 discos para o pino auxiliar, move o disco maior para o destino e depois empilha de novo os n − 1 discos por cima. Com 3 discos são 7 movimentos. Com os 64 discos da lenda seriam cerca de 1,8 × 10^19, mais de 580 bilhões de anos a um movimento por segundo.
Por que o Fibonacci recursivo é tão lento?
O Fibonacci recursivo ingênuo é lento porque recalcula os mesmos valores muitas vezes. Para chegar a F(40) ele faz mais de 331 milhões de chamadas. Esse número cresce de forma exponencial com n. A memoização, que guarda os resultados já calculados, reduz o trabalho a poucas dezenas de passos. É o exemplo clássico de que o desenho do algoritmo pesa mais que o hardware.