• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

neon_prannock

[Desafio] Factorial recursivo

25 mensagens neste tópico

Desta vez, no IRC (#p@p) o desafio era escrever a função que calcula o factorial de um número, recursivamente. Desta forma também podemos demonstrar a muitos programador o método de resolução de algoritmos recursivo que, infelizmente, muitos ainda desconhecem.

E aqui estão os códigos:

Common Lisp:

(defun fact (n)
  (if (= n 0)
      1
      (* n (fact (1- n)))))

Scheme:

(define (fact n)
  (if (= n 0)
      1
      (* n (fact (- n 1)))))

C/C++:

int fact(int n)
{
  return !n ? 1 : n * fact(n-1);
}

C++ (c/ templates):

template<int N> class Factorial {
public:
   enum { value = N * Factorial<N-1>::value };
};

template<> class Factorial<1> {
public:
   enum { value = 1 };
};

Ruby:

def fact( num )
  return 1 if num==0
  num * fact( num-1)
end

Python:

def fact(num):
  if num == 0:
    return 1
  else:
    return num * fact( num-1 )

Java:

import java.math.BigInteger;
class Factorial {
    public static BigInteger fact(BigInteger n) {
        if(n.equals(BigInteger.ZERO))
            return BigInteger.ONE;
        return n.multiply(fact(n.subtract(BigInteger.ONE)));
    }
}

Prolog:

factorial(0,1).
factorial(N,Value) :- NMINUS1 is N-1, factorial(NMINUS1,ValueNMINUS1), Value is N*ValueNMINUS1. 

Dylan:

define method factorial(n :: <integer>)
  if (n == 0)
     1
  else
     n * factorial (n - 1)
  end if
end method factorial

Haskell:

fact 0 = 1
fact n = n * (fact (n - 1))

Visual Basic 6:

Private Function Fact(num As Integer)
If num = 0 Then
    Fact = 1
    Else
        Fact = num * Fact(num - 1)
End If
End Function


Apresentem também esta função nas vossas linguagens para se ir adicionando...

PS: o geshi faz falta ;)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Mas no factorial é importante permitir o cálculo de números de elevadas ordens de grandeza...

Rui Carlos: não seria fact 0 = 1 ?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Em VB6

Private Function Fact(num As Integer)
If num = 0 Then
    Fact = 1
    Else
        Fact = num * Fact(num - 1)
End If
End Function

Cumps

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

"curti" o algoritmo que usaste

só experimentei em scheme

experimenta la fazer

(fact 50000)

vai no minimo "comer" uns 50 MB de RAM

e assim?

(define (fact n)
 (factaux n 1))

(define (factaux n total)
(if (zero? n)
    total
    (factaux (sub1 n) (* n total))))

bem menos

:)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

"curti" o algoritmo que usaste

só experimentei em scheme

experimenta la fazer

(fact 50000)

vai no mínimo "comer" uns 50 MB de RAM

e assim?

(define (fact n)
 (factaux n 1))

(define (factaux n total)
(if (zero? n)
    total
    (factaux (sub1 n) (* n total))))

bem menos

:)

se calhar se usarmos ciclos (caso a linguagem o permita) ainda gasta menos memória e é mais eficiente...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

se calhar se usarmos ciclos (caso a linguagem o permita) ainda gasta menos memória e é mais eficiente...

Sim, o que gasta memória e retrasa o tempo de processamento são os if´s...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Sim, o que gasta memória e retrasa o tempo de processamento são os if´s...

os if's são semelhantes aos ciclos...

o pior são as invocações recursivas que obrigam a estar constantemente a guardar informações na stack de execução do programa.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Em assembly:

factorial:
push ebp
mov ebp, esp

mov eax, [ebp+8]

cmp eax,1
jg @F
jmp @end

@@:	
dec eax
push eax
call factorial
mov ecx, [ebp+8]
xor edx, edx
mul ecx

@end:
mov esp, ebp
pop ebp
ret 4

A função é chamada, exemplo:

push 10
call factorial

e devolve n! em eax

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Aqui fica um exercícizito.

Calcular todos os factoriais de X! a Y! :D

Aqui ficam duas soluções em Python, ambas iterativas.

A primeira:

x = 1
y = 100
while x < y:
j = 1
ii = 1
while ii <= x:
	j *= ii
	ii += 1
print j
x += 1

A segunda (na verdade, foi o que eu escrevi depois de ter pensado melhor no anterior :D) mas que só funciona para x = 1 (quando pensei no exercício não era para dar X, apenas Y):

x = 1
y = 100
j = 1
while x < y:
j *= i
print j
x += 1

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Podias simplesmente passar o while interior para fora, e com o teu j *= i chegavas à mesma solução.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Podias simplesmente passar o while interior para fora, e com o teu j *= i chegavas à mesma solução.

Foi o que eu fiz na segunda.


Agora uma solução recursiva (sim Warrior, esta é para ti :biggrin:):

def factAte(x, y, i = None):
if i == None:
	i = factAte(1, x-1, 1)
	print i
else:
	i *= x
	print i
if x <= y:
	factAte(x+1, y, i)
return i

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Eu tinha feito uma função para isso em Python, tenho de ver se encontro.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Afinal a função não dá, só calcula X! e não de X a Y.

(Não consigo fazer edit ao posto anterior não sei porque... Tentei para aí 7 vezes :D )

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Bem eu hoje iniciei-me no C++ e até puxei conversa sobre isto no canal então cá vai o que fiz

#include <iostream>
using namespace std;

long factorial(long x)
{
  if (x > 1)
   return (x * factorial(x-1));
  else
   return (1);
}
int main()
{
    long de,ate;
    cout << "De: ";
    cin >> de;
    cout << "Ate: ";
    cin >> ate;
    while (de <= ate)
    {
          cout << de << "! = " << factorial(de) << endl;
          de++;
    }
    cin.get();
    cin.get();
    return 0;
}

Pode não estar da melhor forma mas também ainda não sei muita coisa :D e também isto tem limite pois se meteres pa i de 1 a 20 ele "chora" logo apartir de determinada altura :D

e em c#:

static void Main(string[] args)
        {
            long de, ate;
            Console.WriteLine("De: ");
            de = long.Parse(Console.ReadLine());
            Console.WriteLine("Ate: ");
            ate = long.Parse(Console.ReadLine());
            while (de <= ate)
            {
                long fact = factorial(de);
                Console.WriteLine("{0}! = {1}",de,fact);
                de++;
            }
            Console.ReadLine();
        }
        static long factorial(long x)
        {
            if (x > 1)
                return (x * factorial(x - 1));
            else
                return (1);
        }

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Afinal a função não dá, só calcula X! e não de X a Y.

(Não consigo fazer edit ao posto anterior não sei porque... Tentei para aí 7 vezes :D )

Estamos com alguns problemas no forum, ainda não sabemos bem porquê mas estamos a tentar resolver.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Pode não estar da melhor forma mas também ainda não sei muita coisa :D e também isto tem limite pois se meteres pa i de 1 a 20 ele "chora" logo apartir de determinada altura :thumbsup:

Pois chora. Se olhares para o teu algoritmo vês que é bastante ineficiente, porque estás sempre a calcular todo o factorial.

Imagina que fazes de 5 a 6.

Para o 5 vais fazer 1 * 2 * 3 * 4 * 5 e para o 6 vais fazer 1 * 2 * 3 * 4  * 5 * 6, o que não é boa ideia, podes simplesmente pegar no resultado do 5 e multiplicares pelo 6. Estás a perceber o esquema?

E deixo aqui a versão em Haskell :P

factoriais x y = scanl (*) inicio [succ x..y]
   where inicio = product [1..x]

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

O que o Betovsky disse é verdade, mas não é esse o motivo do choro.

Ele chora porque o limite de um int é de 32bits, e o factorial cresce a uma velocidade espantosa, de modo que não é preciso muito tempo para fazer um overflow.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Warrior, tens alguma coisa a apontar em relação à minha solução completamente recursiva?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Em GML:  :-[

factorial de x - fact(x)

script fact:

if argument0==0
return 1
else
return fact(argument0-1)*argument0

factorial entre x e y - fact(x,y)
script fact:

if argument0==argument1
return argument0
else
return fact(argument0,argument1-1)*argument1

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Warrior, tens alguma coisa a apontar em relação à minha solução completamente recursiva?

A tua solução em Python?

Aldrabaste MUITO, é pena não ter aqui interpretador de python para testar..

De qualquer forma, já que queres fazer recursivo (não é a melhor opção para este problema, salta à vista de todos), e pretendes aprender, dou-te duas sugestões: (atenção que eu não programo Python..)

1. Usa duas funções, uma com um ciclo de x a y e outra, recursiva, para calcular factorial(k).

2. Aplica memoization a factorial(k). E mais não digo para te obrigar a pesquisar. Basicamente vais transformar a tua chamada recursiva em O(N), dando-lhe quase a mesma eficiência de uma função iterativa (só perdes no overhead de sucessivas chamadas de funções..)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Estava a falar deste: http://www.portugal-a-programar.pt/forums/topic/0-find-topic/?do=findComment&comment=155793

2. Aplica memoization a factorial(k). E mais não digo para te obrigar a pesquisar. Basicamente vais transformar a tua chamada recursiva em O(N), dando-lhe quase a mesma eficiência de uma função iterativa (só perdes no overhead de sucessivas chamadas de funções..)

Se reparares, é basicamente isso que faço ao passar o 3º argumento... É o mesmo que usar um global i.

EDIT: Correcção da função

def factAte(show, x, y, i = None):
if i == None:
	i = factAte(False, 1, x-1, 1)
	print i
i *= x
if show: print i
if x <= y:
	factAte(show, x+1, y, i)
return i

Removi o else do primeiro if e tirei o print fora do intervalo pretendido.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

O que o Betovsky disse é verdade, mas não é esse o motivo do choro.

Ele chora porque o limite de um int é de 32bits, e o factorial cresce a uma velocidade espantosa, de modo que não é preciso muito tempo para fazer um overflow.

Ahh!!! Bem visto, nem me lembrei desse pormenor. Como ele falou em choro e como o algoritmo era tão mau presumi logo que fosse a referir ao tempo de execução do mesmo.

Em relação a minha solução, não sei porque mas compliquei-a. Aqui fica uma mais simples. É a mesma coisa mas deixa de ser necessário criar uma função extra para o factorial de um número.

factoriais x y = drop x $ scanl (*) 1 [1..y]

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora