Recursive and iterative function that calculates the factorial from 1 to n

3

Good people, I wanted help in a workout:

Asks to create a function that calculates the factorial of numbers from 1 to n. I already have the recursive part, but I do not know how to do it to give me from 1 to n.

def fatorial(n):
    if n == 0 or n == 1:
        return 1 
    else:
        return n * fatorial(n - 1) 

This gives me the factorial of n. I wanted from 1 to n.

And also wanted to know how I do iteratively.

    
asked by anonymous 07.01.2016 / 21:09

4 answers

6

Creating a function that calculates the factorial of a number is one of the easiest recursion-related problems if you know the mathematical definition of a factorial of a number, which is as follows:

f(0) = 1
f(1) = 1
f(n) = f(n - 1) * n, n > 1

Translating this in Python is very easy, since Python is almost pseudo-code.

def f(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    if n > 1:
        return f(n - 1) * n

This function clearly calculates the factorial of n , but what you really want is to calculate the factorial from 1 to n , given a certain n . What you can do is to have another recursive function that calls f from 1 to n (or from n to 1). This function has to save the results somewhere, type in a list. Here is an option to implement such a function:

def _mf_r(n, i, a):
    if i <= n:        
        a.append(f(i))
        _mf_r(n, i + 1, a)
    return a

def mf_r(n):
    return _mf_r(n, 1, [])

And this is my iterative version:

def mf_i(n):
    a = []
    for i in range(1, n + 1):
        a.append(f(i))
    return a

Doing some testing

for i in range(10):
    print(mf_r(i))
    print(mf_i(i))

With results:

[]
[]
[1]
[1]
[1, 2]
[1, 2]
[1, 2, 6]
[1, 2, 6]
[1, 2, 6, 24]
[1, 2, 6, 24]
[1, 2, 6, 24, 120]
[1, 2, 6, 24, 120]
[1, 2, 6, 24, 120, 720]
[1, 2, 6, 24, 120, 720]
[1, 2, 6, 24, 120, 720, 5040]
[1, 2, 6, 24, 120, 720, 5040]
[1, 2, 6, 24, 120, 720, 5040, 40320]
[1, 2, 6, 24, 120, 720, 5040, 40320]
[1, 2, 6, 24, 120, 720, 5040, 40320, 362880]
[1, 2, 6, 24, 120, 720, 5040, 40320, 362880]

In the first output we have an empty list because you wanted the factorial from 1 to n , but the tests start from 0.

    
08.01.2016 / 03:53
7

In fact, the most efficient option in this case is to use the memoization concept in the function, since the factorial of any number n can be obtained by fatorial(n-1) * n as all factorial values will necessarily be calculated from 1 to n , it is true that we have already calculated the value of fatorial(n-1) .

The implementation would be:

def fatorial_range(n):
    """ Retorna o fatorial de todos os números entre 1 e n """
    next_value = 1
    for i in range(1, n+1):
        yield next_value
        next_value *= i + 1

See working at Repl.it | Ideone | GitHub GIST

In this way, the solution becomes O (n), since n will only be multiplied.

To get, for example, factorials up to 5, you would need to do:

for fat in fatorial_range(5):
    print(fat)

Returning:

1
2
6
24
120
    
09.05.2018 / 20:16
2

You can do this using loops or with the math library. Here are 2 examples with user interaction informed the number that you want the factorial. With the for tag:

### Código para calcular fatorial em Python
def fatorial(n):

    for i in reversed(range(1,n)):
        n = n * i
    return n

n = int(input("Digite um numero para calcular seu fatorial: "))

fatorial(n)

resultado = fatorial(n)
print ("O fatorial de ", n , "é: ", resultado)

With the math library:

import math

n = int(input("Digite um numero para calcular seu fatorial: "))

resultado = math.factorial(n)

print ("O fatorial de ", n , "é: ", resultado)

I hope I have helped. Thank you.

Edited: Sorry. I misunderstood the questioning of the colleague's question. Here is my corrected answer below. Code in Python to calculate the factorial from 1 to n terms. Thank you.

With loop :

### Calcular fatorial do 1 até n termos com laço for em Python

def fatorial(j):

    for i in reversed(range(1,j)):

        j = j * i
    return j

n = int(input("Digite o numero de termos que deseja calcular o fatorial: "))

for j in range(1,n+1):
    print ("O fatorial de ", j , "é: ", fatorial(j))

With the math library:

### Calcular fatorial de 1 até n termos com a biblioteca math em Python

import math

n = int(input("Digite o numero de termos que deseja calcular o fatorial: "))

for i in range(1,n+1):
    resultado = math.factorial(i)
    print ("O fatorial de ", i , "é: ", resultado)
    
08.06.2018 / 16:12
2

I clicked on the site to evaluate any solution, after thinking for a moment, formulated functions that I think are more efficient. (In python)

for x factorial:

def fatorial(x):
    result=1
    for i in range(x):
        fator_i=(x-i)
        result=result*fator_i
    return result

More compact and correctly matches cases x = 0, x = 1, no need to test if.

To satisfy your request, I thought of a simple loop, to form the list of factorials of i, varying from one natural to the other, including the particular case you wanted (from 1 to n) (a = 1, b = n):

def lista_fat(a,b):
    lista=[]
    for i in range(a,b+1):
       lista.append(fatorial(i))
    print'lista dos fatoriais de', a, 'ao',b
    print lista

Below the whole code, with the particular case of 1 to 10.

def fatorial(x):
    result=1
    for i in range(x):
        fator_i=(x-i)
        result=result*fator_i
    return result

def lista_fat(a,b):
    lista=[]
    for i in range(a,b+1):
        lista.append(fatorial(i))
    print'lista dos fatoriais de', a, 'ao',b
    print lista

lista_fat(1,10)

EDIT, syntax for Python 3:

def fatorial(x):
    result=1
    for i in range(x):
       fator_i=(x-i)
       result=result*fator_i
    return result

def lista_fat(a,b):
    lista=[]
    for i in range(a, b+1):
       lista.append(fatorial(i))
    print('lista dos fatoriais de {} ao {}'.format(a, b))
    print(lista)

lista_fat(1,10)

Result:

 lista dos fatoriais de 1 ao 10
 [1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800]
    
09.05.2018 / 19:38