Factorial. Another algorithm


#1

I was doing the exercise and I solved it differently.

def factorial(x):
    x = int(x)
    number = 1
    mult_num = 1
    attempt = 0
    while attempt != x:
        number = number * mult_num
        mult_num += 1
        attempt += 1
    return number
    
print factorial(raw_input("put some number: "))

I think it is logically true. However, the built-in (I mean that which the site offered) is more simply.

def factorial(x):
    if x == 1 or x == 0:
        f = 1
        return f
    else:
        f = x * factorial(x - 1)
    return f

But I didn't understand how it works((

Sorry for my bad English. And I'd be grateful if smo could explain me in penguin way))


#2

Your second code part is called "recursion". It's a function which called itself again, until its finished (or never ends...). It's used often in math (for example: Fibonacci number). In math you will write as example: 4!. It stands for 4*3*2*1

The if part just check if there is a 0 or 1 deliver, thats basically give you 1 back.
The else part takes the value of x and multiple itself with the value of x subtract by 1.
That continue until all digits are looped/done.

In my else part i just written:

else:
        return x * factorial(x-1)

So factorial(3) will returns 6 to me.
3 * 2 * 1
6 * 1 = 6

With factorial(4) you will have 24.
4 * 3 * 2 * 1
12 * 2 * 1
24 * 1 = 24

Recursion means “defining something in terms of itself”. Just search for python recursion and you will get much stuff to read, as example the openbookproject website have some good explanation.

If you want more explanation, someone else ask the same question in another thread: Link


#3

Thank you for your attention. I couldn't understand how looping works. As far as I understood

# let's take x=4 as an example
def factorial(4):
      if 4 == 1 or 4 == 0 #it is not true so we'll pass it
            f= 1          #pass
            return f      #pass
      else:
            f = 4 * (4-1)
      return 12           #here is I'm hesitating. will it return the value to factorial?

So I couldn't find in which part it multipies 12 to 3 and etc.


#4

I modded my code a little bit and build in some prints for you. So the code looks a bit unclear at first, because of the print statements. It should show you what happens inside.

def factorial(n):
    print "factorial called with n = ", n
    if n <= 1: 
        return 1
    else:
        total = n * factorial(n-1)
        print "interim result for ",n," * factorial(",(n-1),"): ",total
        return total

print factorial(4)

When you execute it, you will get the echo:

factorial called with n = 4
factorial called with n = 3
factorial called with n = 2
factorial called with n = 1
interim result for 2 * factorial( 1 ): 2
interim result for 3 * factorial( 2 ): 6
interim result for 4 * factorial( 3 ): 24
24

The recursion function call its body multiple times. The processing runs internally. I guess it will saved first all in a stack/list (n count down from 4 to 1), Than the machine call and process it reverse (The part with 2*1, 3*2, 4*3).

Hope that help you a bit.


#5

Now it make sense. I've experimented some and I found out that it's all about

factorial(n-1) and rеturn

Earlier I couldn't understand how numbers were multiplying several times without using FOR or WHILE.
With your help I could monitor the process and some tests showed me that when RETURN returns another value DEF goes on working till there is nothing to change. As an example:

def factorial(8):       
    print "factorial called with n = ", 8
    if 8<10:       # it is True so let's continue
        n+=1      # n=9
        return factorial(9)    
        
print factorial(8)

On monitor:
factorial called with n = 8

def factorial(9):       
    print "factorial called with n = ",9
    if 9<10:       # it is True so let's continue
        n+=1      # n=10
        return factorial(10)    
        
print factorial(9)

On monitor:
factorial called with n = 9

def factorial(10):       
    print "factorial called with n = ", 10
    if 10<10:       # it is True so let's continue
        n+=1      # n=11
        return factorial(11)    
        
print factorial(10)

On monitor:
factorial called with n = 10

def factorial(11):       
    print "factorial called with n = ", 11
    if 11<10:       # it is NOT True 
        n+=1        # stop
        return factorial(11)    #stop
        
print factorial(10)

On monitor:
None

--Nothing changed so on monitor we see None--
--It tests another time, also nothing changed--

On monitor:
None

Eventually, it stops working

It is how I understood))) Thank you once more


#6

I'm glad that i could help you.
Give google a try for "python factorial", there are many examples if you want to learn more about factorial.
Cheers


#7

I think this is a mistake from codeacademy and I will try to pass this by doing it the hard way. But if you try this it lets you pass lool:

import math
def factorial(x):
..... return math.factorial(x):


#8

"""The while doesn't break in your case and goes in endless loop: I did it with 'for in ()' loop"""

def factorial (x):
number = 1
value = 1
attempt = 0
x = int(x)
for attempt in range(1, x+1):
#while attempt != x: (Not useful)
number = number * value
value = value + 1
atempt = attempt + 1
print"output", number
if (attempt == x):
break
return number
print factorial(raw_input("What you need for factorial:"))


#9

This topic was automatically closed 7 days after the last reply. New replies are no longer allowed.