Sobre Recursividade

Cambalinho · 18 de março de 2013

eu ja vi isto em outras linguens mas nao percebo como se faz. só sei que é a 'chamar a propria funçao' e que faz 1 especie de ciclo. alguem me pode explicar isto melhor e como posso usar.

(nao interessa se nao usarem liguagem C\C++... eu queria aprender mais sobre isto)

ScreenBlack · 18 de março de 2013

Como você comentou, recursividade é chamar a própria função.

A rotina executada antes de ser chamada novamente a função, será empilhada, até a recursividade finalizar.

Nesse link explica bem como funciona.

Espero que ajude.

Cambalinho · 18 de março de 2013

Como você comentou, recursividade é chamar a própria função.
A rotina executada antes de ser chamada novamente a função, será empilhada, até a recursividade finalizar.

Nesse link explica bem como funciona.

Espero que ajude.

podes me mostrar 2 funçoes diferentes e simples de recursividade e me explicar como funciona?

(desculpa se te estou a dar muito trabalho, mas sei que a recursividade mal empilhada pode dar erros estranhos ou ciclos infinitos)

anonimo1w · 18 de março de 2013

Cambalinho, vou tentar fazer de cabeça pra te ajudar, aqui duas das mais famosas (fatorial e fibonacci) ok?


int fatorial(int n)  //n!, ex: 3!= 3*2*1=6
{
   if(n<=1)  //vi no wikipedia e vim corrigir.. se fosse menor que 0 iria dar em loop infinito.. 
     return 1;
   else
    return n*fatorial(n-1);
}


int fibonacci(int n)
{
  if(n==0)
   return 0;
  else if(n==1)
   return 1;
  else
   return fibonacci(n-1)+fibonacci(n-2);
}

ps: fiz de cabeça, então podem estar erradas (principalmente a de fibonacci), mas isso é meio que a base, ok?

infelizmente (e isso você deve saber) recursivas são mais lentas que iterativas, pela chamada de ciclos, principalmente, então não acho, exatamente, uma boa ideia (bom, posso estar errado xD)

Matheus Maldi · 18 de março de 2013

int fib(int x)
{
	if (x < 2)
		return 1;
	else
		return fib(x -1) + fib (x -2);
}

int fatorial(int x)
{
	if (x < 2)
		return 1;
	else
		return x * fatorial(x-1);
}

ScreenBlack · 18 de março de 2013

Ótimos exemplos apresentados acima pelos colegas.

A recursividade, como dito, é um empilhamento de chamadas. O retorno da execução da última chamada recursiva será utilizada pela penultima, podendo ou não haver tratamentos e então, retornada para a anti-penultima, e assim, sucessivamente.

A recursividade é sem dúvida, uma execução mais demorada e que consome mais memória (a não ser que use ponteiros), devido a todo o conteúdo da rotina ir pra memória até o alcance da última chamada recursiva.

O maior cuidado a ser tomado em chamadas recursivas, é garantir que haverá um controle que identifique o seu término, e esse será sempre antes da chamada recursiva.

Listeiro 037 · 19 de março de 2013


int fibonacci(int n)
{
  if(n==0)
   return 0;
  else if(n==1)
   return 1;
  else
   return fibonacci(n-1)+fibonacci(n-2);
}

Aproveitando, como é que se proibe essa função de receber n negativo? É só com o tal unsigned int?

De resto, eu ousaria escrever assim:

int fibonacci(int n)
{
  if(n==0 || n==1) return n;
  return fibonacci(n-1)+fibonacci(n-2);
}

LNW · 19 de março de 2013

Salve Listeiro, anda sumido..

Aproveitando, como é que se proibe essa função de receber n negativo? É só com o tal unsigned int?

Depende, você quer fazer tipo um teste de consistência?

int fibonacci(int n)
{
    if ( n==0 || n==1 ) return n;
    if (n < 0) return -1;
    return fibonacci(n-1) + fibonacci(n-2);
}

Para qualquer número negativo ele retornaria -1...

Abs

LNW

Listeiro 037 · 19 de março de 2013

Salve Listeiro, anda sumido..

Salve!

Depende, você quer fazer tipo um teste de consistência?
int fibonacci(int n)
{
    if ( n==0 || n==1 ) return n;
    if (n < 0) return -1;
    return fibonacci(n-1) + fibonacci(n-2);
}
Para qualquer número negativo ele retornaria -1...

Sim, no caso retornar -1 só seria necessário se fosse usado int ao invés de unsigned int?

int reduz a variável à metade da capacidade se não forem necessários valores negativos. Você citou o -1 e eu me lembrei de que em outros casos usam NULL.

Mas nesse caso a consistência ainda é simples. Se por exemplo, fosse feito um cálculo anterior no meio do código e fosse computado um valor negativo. Com "int" há o reconhecimento do estouro, com "unsigned int" dobra-se o número de bits dos cálculos, mas perde-se nesta forma mais simples de reduzir a depuração.

Na chamada à função, a consistência ficaria melhor se fosse resolvida no código ou internamente? Com sub-rotina de tratamento de erro, isso pensando bem mais longe? Ou de modo algum compensa "unsigned int"?

airtonbjunior · 20 de março de 2013

Pode ver algumas explicações sobre recursividade nesse link rsrs.

Abraços.

Cambalinho · 20 de março de 2013

Pode ver algumas explicações sobre recursividade nesse link rsrs.
Abraços.

então mandas-me para o mesmo link(topico)? lol

airtonbjunior · 20 de março de 2013

então mandas-me para o mesmo link(topico)? lol

Pegou o espírito da recursão!

Abs.

Cambalinho · 20 de março de 2013

Pegou o espírito da recursão!

Abs.

lol essa esta boa lol

desculpem mas podem me explicar melhor esta linha:

return x * fatorial(x-1);

é que usa return e esta-me a confundir:(

ScreenBlack · 20 de março de 2013

Digamos que "x" tenha recebido por parâmetro valor 3 e que o limite seja "x == 1"


[empilhando] primeira chamada: x = 3
[empilhando] segunda chamada: x = 2
[empilhando] terceira chamada: x = 1
[desempilhando] terceira chamada: retorna 1
[desempilhando] segunda chamada: retorna "2 * 1 = 2"
[desempilhando] primeira chamada: retorna "3 * 2 = 6"

Espero não ter confundido mais ainda. rs

Cambalinho · 20 de março de 2013

Digamos que "x" tenha recebido por parâmetro valor 3 e que o limite seja "x == 1"
[empilhando] primeira chamada: x = 3
[empilhando] segunda chamada: x = 2
[empilhando] terceira chamada: x = 1
[desempilhando] terceira chamada: retorna 1
[desempilhando] segunda chamada: retorna "2 * 1 = 2"
[desempilhando] primeira chamada: retorna "3 * 2 = 6"
Espero não ter confundido mais ainda. rs

imaginando que x=3, então:

return 3 * factorial(3-1);

que neste é 3 * fatorial(2);

olha 1 coisa isto nao pode ser feito sem o return?

ScreenBlack · 20 de março de 2013

não é possível sem o return, pois é ele quem vai retornar o valor para a chamada anterior.

Cambalinho · 20 de março de 2013

não é possível sem o return, pois é ele quem vai retornar o valor para a chamada anterior.

entendi... mas o resultado da multiplicaçao fica a onde?

3!= 3*2*1

eu fiz este codigo:

#include <stdio.h>


int SomaFactorial(int n)
{
	if (n<=1) return 1;
	return n + SomaFactorial(n-1);
}

void main()
{
	int a=5;
	int b=0;
	b=SomaFactorial(a);
	printf("%d",;
}

com 'a' é 5 então fica: 5 + 4+3+2+1.

a minha questao: eu nao sei o que estou a enviar no 'return'

eu sei que me dá esse resultado porque copiei pela do factorial(em vez de multiplicaçao meti soma). mas como é que estou a enviar o resultado e n-1?

ScreenBlack · 20 de março de 2013

Os resultados ocorridos devido o retorno do empilhamento, não será armazenado dentro da rotina, mas sim, na área de memória referente a pilha de execução (que é o return). Quando terminar de desempilhar, o resultado será atribuído a variável 'b', no seu caso.

Cambalinho · 20 de março de 2013

Os resultados ocorridos devido o retorno do empilhamento, não será armazenado dentro da rotina, mas sim, na área de memória referente a pilha de execução (que é o return). Quando terminar de desempilhar, o resultado será atribuído a variável 'b', no seu caso.

muito obrigado

(sao coisa que nunca passam nos manuais lol)

eu sei que C\C++ tem mts cenas destas, o que torna mais difícil de compreender. como isto:

if(varname) something;

o que quer dizer é:

if(varname!=0) something;

porque em C\C++, '!=0' quer dizer positivo.

muito obrigado por tudo

Listeiro 037 · 21 de março de 2013

lol essa esta boa lol

desculpem mas podem me explicar melhor esta linha:
return x * fatorial(x-1);
é que usa return e esta-me a confundir:(

Vamos dizer que recursão segue um modelo semelhante ao do conjunto dos Números Naturais. Também está relacionado ao Princípio de Indução Finita.

Recursões trabalham com conjuntos que possuem um valor mínimo. Semelhante ao dos Naturais.

0, 1, 2, 3, 4 ... mesmo que comece em um número maior 4, 5, 6, 7, 8 ... ou menor -3, -2, -1, 0, 1, 2 ... tem que ter uma correspondência de 1 para 1 com os Naturais. Ou seja, não é um poço sem fundo.

Isso ocorre porque na recursão a função solicita-se a ela mesma. Ela não fica se solicitando eternamente. Há um ponto final, que é semelhante ao de conjuntos com um valor mínimo. Ela pára nesse análogo de menor valor de conjunto.

No caso dos fatoriais, o limite ocorre em 0 e 1, na verdade em zero. Como o valor de 0 e 1 coincidem, aproveita-se para fazer um "if (x==0 || x==1) return ... ;" ou "if (x<=0) ... " porque a definição de zero fatorial é 1 e não há definição (neste caso, mas é outra história) de fatoriais para negativos, o que daria algum erro no funcionamento e que necessitaria ser tratado no código, se for ser bem rigoroso.

A comparação em conjunto de 0 e 1 é porque economiza uma chamada recursiva e em certos casos o programa fica mais rápido.

Existem outros modelos de funções recursivas, além das de fatoriais, fibonacci, particionamento, mdc. Sempre prevenindo-se contra a memória do computador não comportar as informações das tantas chamadas. Senão esse local da memória, como dizem, "estoura".

Cambalinho · 21 de março de 2013

Vamos dizer que recursão segue um modelo semelhante ao do conjunto dos Números Naturais. Também está relacionado ao Princípio de Indução Finita.
Recursões trabalham com conjuntos que possuem um valor mínimo. Semelhante ao dos Naturais.

0, 1, 2, 3, 4 ... mesmo que comece em um número maior 4, 5, 6, 7, 8 ... ou menor -3, -2, -1, 0, 1, 2 ... tem que ter uma correspondência de 1 para 1 com os Naturais. Ou seja, não é um poço sem fundo.

Isso ocorre porque na recursão a função solicita-se a ela mesma. Ela não fica se solicitando eternamente. Há um ponto final, que é semelhante ao de conjuntos com um valor mínimo. Ela pára nesse análogo de menor valor de conjunto.

No caso dos fatoriais, o limite ocorre em 0 e 1, na verdade em zero. Como o valor de 0 e 1 coincidem, aproveita-se para fazer um "if (x==0 || x==1) return ... ;" ou "if (x<=0) ... " porque a definição de zero fatorial é 1 e não há definição (neste caso, mas é outra história) de fatoriais para negativos, o que daria algum erro no funcionamento e que necessitaria ser tratado no código, se for ser bem rigoroso.

A comparação em conjunto de 0 e 1 é porque economiza uma chamada recursiva e em certos casos o programa fica mais rápido.

Existem outros modelos de funções recursivas, além das de fatoriais, fibonacci, particionamento, mdc. Sempre prevenindo-se contra a memória do computador não comportar as informações das tantas chamadas. Senão esse local da memória, como dizem, "estoura".

muito obrigado