53
Realmente recursão é sobrevalorizada.
Eu percebo que o ensinamento de função recursiva não costuma ser feito do jeito certo (na minha opinião, claro) quando o exemplo sempre usado é para fazer algo que é sequencial e não recursivo. Claro que ele pode ser recursivo, mas recursão vai bem quando você vai explodindo execuções subsequentes usando o mesmo critério....
respondida 11/01/16 às 4:12
30
Problema real
Os algoritmos são completamente diferentes. Por isto quanto mais você executar ele fica pior.
Em C está chamando
fibo(num - 1) + fibo(num - 2)
Em Java está
fibo(num - 1) + (num - 2)
O primeiro chama a mesma função duas vezes. O segundo apenas uma. Em Java nem dá o resultado certo. Portanto ele é muito pior que em C. Antes de um algoritmo ser ...
respondida 25/11/14 às 7:03
29
A resposta depende muito do contexto.
Situações em que usar recursão
Quando o desempenho for igual ou superior à versão iterativa do código
Há várias situações onde usar recursão é mais eficiente.
Uma delas é quando se sabe de antemão que não haverão muitos níveis de chamada e a versão iterativa gastaria mais processamento e memória com uma pilha de ...
respondida 16/06/14 às 18:14
utluiz
71,1mil88 medalhas de ouro140140 medalhas de prata243243 medalhas de bronze
26
TL;DR
Todo código recursivo pode ser traduzida numa forma iterativa, porém alguns algoritmos são naturalmente recursivos e mais facilmente representados desta forma.
Pense, por exemplo, em percorrer todos os nós de uma árvore ou grafo, processar todos os arquivos de um diretório e subdiretórios e assim por diante.
No modo iterativo você é responsável por ...
respondida 11/01/16 às 4:28
utluiz
71,1mil88 medalhas de ouro140140 medalhas de prata243243 medalhas de bronze
23
A diferença é justamente aonde a chamada recursiva é chamada: Caso ela seja chamada na "cauda" da função, é uma chamada de cauda recursiva.
A "cauda" da função é sua última chamada. É a última computação / cálculo feito pela função, e logo depois dela, nenhum tratamento é feito antes de retornar seu valor.
Por exemplo, considerando esta função para ...
respondida 5/02/14 às 12:07
André Leria
4.96722 medalhas de ouro1818 medalhas de prata4444 medalhas de bronze
19
Vamos considerar o trecho de código que você colocou na pergunta, apenas atribuindo o retorno da chamada a uma variável, para simplificar a explicação:
def fibonacci(n):
if n <= 1:
return n
else:
return fibonacci(n-1) + fibonacci(n-2)
resultado = fibonacci(5)
A memória no computador possui um endereço e um valor. Para fins ...
respondida 31/05/17 às 22:58
Woss
71,4mil1414 medalhas de ouro104104 medalhas de prata189189 medalhas de bronze
14
Operador ternário
O operador ternário se assemelha a um if mas é uma expressão e não um statement. Então você pode usar em qualquer lugar que aceite uma expressão, desde que os seus resultados também sejam expressões. Na verdade prefiro chamá-lo de condicional, já que ternário é circunstancial e não define o que ele faz.
Ele é composto de três partes (por ...
respondida 28/09/14 às 23:08
13
Concordo com a resposta do utluiz, gostaria somente de dar o seguinte complemento:
Considerando que uma linguagem de programação sendo usada possua os dois recursos...
Possuir os dois recursos não basta, também é importante saber se eles são implementados com eficiência e se são usados extensivamente em programas escritos naquela linguagem.
Quanto à ...
respondida 19/06/14 às 9:31
mgibsonbr
79,4mil2121 medalhas de ouro170170 medalhas de prata314314 medalhas de bronze
12
Funções recursivas são uma vantagem para casos em que o problema seja naturalmente definido em função de si mesmo, e em que a solução recursiva seja a mais simples. No início isso pode parecer estranho já que recursão parece complicada e confusa, mas com o tempo e com o entendimento (muita prática também) você aprende a identificar problemas em que ela é a ...
respondida 11/01/16 às 4:38
BrunoRB
5.37811 medalhas de ouro1414 medalhas de prata3131 medalhas de bronze
11
Primeiro vou responder o título ("Uma função recursiva pode substituir while e for?") de maneira geral, depois falaremos sobre o código específico da pergunta.
Uma função recursiva pode substituir while e for?
De maneira geral, qualquer algoritmo iterativo pode ser convertido para um recursivo e vice-versa. Mas só porque pode, não quer dizer que ...
respondida 6/03/20 às 11:29
hkotsubo
50,1mil1616 medalhas de ouro4949 medalhas de prata102102 medalhas de bronze
10
Uma variável estática (declarada dentro de um método) irá manter seu valor entre chamadas sucessivas. Se você não deseja manter o valor entre chamadas sucessivas, por que não simplesmente usar variáveis locais (não estáticas)? O fatorial recursivo poderia ser implementado de forma mais simples (inclusive sem variáveis locais ou estáticas):
unsigned long ...
10
No geral, as respostas até o momento tratam a mensuração da eficiência em termos práticos.
Vou dar uma resposta em termos teóricos, já que você faz duas perguntas: Como determinar as equações de complexidade e se há outro método.
Para responder a primeira pergunta, em primeiro lugar recomendo um livro introdutório de algoritmos que ensine notação Big-O.
...
9
O problema não é exponencial, é linear, mas é linear no número de ancestrais da pessoa: não tem como garantir que João não é ancestral de Maria sem examinar todos ancestrais de Maria.
Dá até para reduzir isso um pouco, eliminando ancestrais já examinados (uma mesma pessoa pode aparecer mais de uma vez como ancestral -- casamento entre primos, por exemplo), ...
9
Imagino que entenda bem sobre recursão, quando usar e sua vantagem em relação ao laço.
Também deve saber como funciona a pilha de chamadas e que a memória para isto tem um tamanho fixo determinado no início da execução, provavelmente colocado pelo compilador ou linkeditor.
Se o código de uma função chama a si própria, em cada chamada gerará um novo stack ...
respondida 17/02/17 às 3:42
9
Primeiro, a função está errada, tem um print a mais e a segunda chamada recursiva trocou a ordem das torres:
def hanoi(disc, ori, dest, aux):
if disc == 1:
print('Move disc {} from tower {} to the tower {}'.format(disc, ori, dest))
return
hanoi(disc - 1, ori, aux, dest)
print('Move disc {} from tower {} to the tower {}'.format(...
respondida 25/09/19 às 19:00
hkotsubo
50,1mil1616 medalhas de ouro4949 medalhas de prata102102 medalhas de bronze
8
Em primeiro lugar quero salientar uma importante diferença de termos:
Tail Call Optimization: Quando uma implementação otimiza uma chamada em cauda de forma que um novo stack frame não seja alocado e o caller seja utilizado, criando um acrescimo zero de memoria. Repare que isso é uma otimização, ou seja, é opcional e não se deve assumir que acontecerá. Ela ...
respondida 27/01/14 às 20:12
Guilherme Bernal
19,8mil11 medalhas de ouro4949 medalhas de prata9494 medalhas de bronze
8
As tuas condições estão incompletas.
Um array de N elementos é composto de números crescentes quando o array mais pequeno com os primeiros N - 1 é composto de números crescentes e o penúltimo elemento do array não é maior que o último. Ou seja
// chamar função com array de 0 elementos é Comportamento Não Definido
int analisa(int *v, size_t n) {
if (n ==...
7
Como outros já mencionaram, C# não te dá uma garantia de que uma recursão de cauda vai ser otimizada. Eu sou muito fã de recursão de cauda mas acho que que você está focando um pouco no sentido errado - eu acho que o controle de fluxo flexível é um ponto mais crucial da recursão de cauda do que a imutabilidade e isso muda um pouco a maneira de abordar esse ...
7
O que realmente faz isso?
return n + sum( n - 1);
O método sum() fica se chamando sempre passando como parâmetro o próprio número que recebeu como argumento menos um, até que esse número chegue a zero que será quando ele retornará zero. Ou seja, se você passar o número 8, ele vai retornar 8 mais o retorno do método sum(7), que vai retornar 7 mais o ...
respondida 3/02/16 às 17:04
7
return n + sum( n - 1):
Nesta linha é somado o valor de n com o valor resultante do método sum(n-1).
No exemplo:
sum(8) = 8 + sum(7)
sum(7) = 7 + sum(6)
sum(6) = 6 + sum(5)
sum(5) = 5 + sum(4)
sum(4) = 4 + sum(3)
sum(3) = 3 + sum(2)
sum(2) = 2 + sum(1)
sum(1) = 1 + sum(0)
sum(0) = 0.
Repare que sum(0) não chama o método sum novamente. Este é o ponto de ...
7
Me baseei nessa fórmula e cheguei neste algoritmo:
#include <stdio.h>
#include <math.h>
int hiperfatorial(int n) {
double ret = 1.0;
do ret *= pow(n, n); while (n-- > 1);
return (int)ret;
}
int main(void) {
int n;
printf("\nDigite um numero: ");
scanf("%d", &n);
printf("\nO ...
respondida 16/11/17 às 18:52
7
Sobre a sua solução, você não está resgatando o valor da função em uma variável. Parece que tem uma ideia implícita em seu código que o valor da variável resultado está sendo alterada na pilha de recursão, mas isso não ocorre.
Toda variável em C é passada por valor, não por referência (mais sobre o assunto). O que se chama de passagem por referência em C é a ...
respondida 16/11/17 às 23:10
Jefferson Quesado
21,7mil33 medalhas de ouro4646 medalhas de prata121121 medalhas de bronze
7
Em C temos funções e não métodos. Variáveis não são recursivas, porque para haver recursão precisa de uma ação e variável é estado.
Em geral ele pode ser usando no lugar de um laço de repetição. Na maioria das vezes não deveria. Deixe a recursão para casos onde ela seja mais intuitiva. Sequências normais funcionam melhor em laços. É possível transformar este ...
respondida 21/08/18 às 18:21
7
Você pode utilizar a recursão para passar como parâmetro o último array gerado até chegar no tamanho desejado:
const montar = (opcoes, calculado = []) => {
// Verifica o critério de parada, que neste caso é já ter preenchido todas as posições do array
if (opcoes.length === calculado.length) {
return [calculado];
}
let novos = [];
...
respondida 22/02/19 às 18:43
Sorack
26,7mil22 medalhas de ouro3131 medalhas de prata9090 medalhas de bronze
7
Esse é um caso que para você entender como foi desenvolvido a função para resolver a torre de Hanoi você precisa considerar que já existe uma função para resolver a torre de Hanoi. Confuso? Não, recursivo.
Vamos considerar que nosso objetivo é passar os discos de A para C, sendo B nosso auxiliar. Para que o resultado seja válido, o disco 3 deve ser o ...
respondida 25/09/19 às 18:59
Woss
71,4mil1414 medalhas de ouro104104 medalhas de prata189189 medalhas de bronze
7
Se implementares recursividade para valores elevados, com mil por exemplo vai retornar um erro:
recursion error maximum recursion depth exceeded
É uma proteção contra o stack overflow, sim. O Python (ou melhor, a implementação do CPython) não otimiza a recursão, e a recursão desenfreada causa este problema. Você pode verificar o limite permitido pela ...
respondida 5/03/20 às 20:58
Ernesto Casanova
1.30611 medalhas de ouro44 medalhas de prata1010 medalhas de bronze
7
Isso é chamado recursão. Acho que o grosso da explicação está em O que é um método recursivo?.
Há uma repetição sim, só não há um comando de controle que diga para repetir, a repetição se dá justamente por a função chamar a si própria. Se chama algo várias vezes está repetindo a chamada.
Como uma estrutura como um while ou for sabe que deve ...
respondida 24/06/20 às 4:17
6
Bem, eu não entendo profundamente de compiladores ou interpretadores, portanto vou me ater aos fatos que encontrei em documentações e referências.
Em tese, Javascript poderia ter a otimização de chamadas "em cauda". De fato, existe uma implementação especial que já possui este recurso: RhynoWithContinuations. Esta é uma versão do Rhyno, uma implementação ...
respondida 27/01/14 às 17:18
utluiz
71,1mil88 medalhas de ouro140140 medalhas de prata243243 medalhas de bronze
6
Seu problema está aqui:
cod(ord(i))
Você está chamando a função cod recursivamente passando o resultado de ord - e portanto um inteiro - como argumento. Mas como a primeira coisa que cod faz é iterar sobre o argumento:
for i in n: # n na segunda chamada é o resultado de ord(i)
Então ele reclama que não pode iterar sobre um inteiro.
Como você está usando ...
respondida 9/12/15 às 19:21
mgibsonbr
79,4mil2121 medalhas de ouro170170 medalhas de prata314314 medalhas de bronze
6
É só fazer uma verificação se fl é um diretório usando File.isDirectory() e chamar o método novamente passando fl como parâmetro.
private static List<File> listarArquivos(File source)
{
List<File> fileList = new ArrayList<>();
File[] list = source.listFiles();
for (File fl : list) {
if (!fl.isDirectory()) {
...
respondida 2/12/16 às 11:44
LINQ
66,1mil1212 medalhas de ouro111111 medalhas de prata210210 medalhas de bronze
Apenas as respostas wiki não pertencentes à comunidade mais votadas e de um tamanho mínimo se qualificam
Tags relacionadas
recursão × 234c × 55
python × 52
java × 41
python-3.x × 29
funções × 28
javascript × 17
array × 12
php × 10
c++ × 10
loop × 10
lista × 9
algoritmo × 9
c# × 7
programação-funcional × 6
árvore-binária × 6
query × 5
lógica × 5
mysql × 4
sql × 4
banco-de-dados × 4
sql-server × 4
desempenho × 4
fibonnaci × 4
node.js × 3