4
Good people, wanted help with an exercise:
It asks to create a function that calculates the factorial of the numbers from 1 to n. I already have the recursive part, but I don’t know how to make it 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 I also wanted to know how I do it iteratively.
11
Creating a function that calculates the factorial of a number is one of the easiest recursion-related problems if you know the mathematical factorial definition of a number, which is the following:
f(0) = 1
f(1) = 1
f(n) = f(n - 1) * n, n > 1
Translating this into 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 factor of n, but what you really want is to calculate the factor of 1 until n, given a certain n. What you can do is have another recursive function that calls f starting from 1 until n (or of n up to 1). This function has to save the results somewhere, like 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
Running some tests
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 of 1 until n, but the tests start from 0.
To the author of the question: in practice, use the iterative version. The recursive versions are good as study, but are less efficient.
Thank you! : ) I was very enlightened!
8
In fact, the most efficient option in this case is to use the concept of memoization in the function, since the factorial of any number n can be obtained by fatorial(n-1) * n and how all factor values 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 on Repl.it | Ideone | Github GIST
Thus, the solution is O(n), as only n multiplications will be made.
To obtain, for example, factorial up to 5, it would be enough to do:
for fat in fatorial_range(5):
print(fat)
Returning:
1
2
6
24
120
Wow, solved the "problem" of recursive ninja mode xD +1 ... I think the boost ai must have been about 300%
Anderson, correct me if I’m wrong, but you didn’t use memoization in its answer, but rather implemented mathematically intelligent algorithm. Memoization is a type of cache and you do not save or recover the results already obtained.
I know the question is old, my fear is that someone confuses the term memoization when you fall here, because your answer is good.
@fernandosavio so I commented that I applied the "concept of memoization". I defined a generator that calculates the values and how the generator maintains the context between the calls, the value of the previous factor is in memory, just "increment it". For being an access to memory and not a recalculation of value I said that the concept was applied.
But you can’t take a value that’s already been returned, so I guess it’s not memoization. It’s an intelligent and performative way, but no memoization.
Forget it, now it’s over. The code itself is not memoization but the concept to solve the problem is. It was bad
@exact design. The concept of memoization is to cache a value previously calculated so as not to have to recalculate it. That’s what I did inside the generator, always keeping the last factorial calculated in memory, because at the time to calculate the factorial of 5, for example, the factorial of 4 is in memory, can only make "5 * fat(4)".
2
I clicked on the site to evaluate any solution, after thinking for a moment, I formulated functions that I find more efficient. (In python 2.x and 3.x)
for factorial of x:
def fatorial(x):
result=1
for i in range(x):
result=result*(x-i)
return result
More compact and properly meets the cases x=0, x=1, no need to test if.
To satisfy his request, I thought of a simple loop, to form the list of factorials of i, ranging from one natural to, to another b, 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 1 to 10.
def fatorial(x):
result=1
for i in range(x):
result=result*(x-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)
EDITING, syntax for Python 3:
def fatorial(x):
result=1
for i in range(x):
result=result*(x-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)
Upshot:
lista dos fatoriais de 1 ao 10
[1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800]
Browser other questions tagged python python-2.7
You are not signed in. Login or sign up in order to post.
Dude, if this is a college exercise in programming logic, make an effort to.
– Puam Dias
But I can’t do it... so I’m asking for help.
– CSAnimor
This kind of question devalues the site
– sergiopereira