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/