5. factorial


#1


  1. loops- practice makes perfect 5. factorial

    Oops, try again. factorial(2) returned 1 instead of 2


def factorial(n):
    y=1
    while(n>0):
        
        y=1*n
        n=n-1
        
    return y

print factorial(4)


#2

Hi, @chipslayer98995 ,

What is the purpose of this statement, and does it accomplish that purpose? ...

y=1*n

#3

[quote="chipslayer98995, post:1, topic:67584"]

You should use this code:

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

@ajaxace03753 In this example I used from Recursion and in Computer Science Recursion is the process of repeating items in a self-similar way.
and you should google for recursion http://stackoverflow.com/questions/3021/what-is-recursion-and-when-should-i-use-it


#4

Hi @ajaxace03753 ,

Please provide an explanation of the code that you posted, so that users who read it can understand what it does. A solution posted without an explanation tempts other users to copy and paste it without their first learning to understand it.


#5

Thanks, @ajaxace03753, for the link to information about recursion.


#6

I'm confused with how @ajaxace03753's code works. I would think that it would just keep returning the reduced "n" value, hence ultimately returning a 1 or 0. How does the code know to store the answer from previous "returns" in the loop?


#7

Okay, so let's say n = 4. Checking the if statement we can see that 4 != 0, so we execute the else statement. Here is where the recursion happens. We substitute 4 into n * n -1 which gives us 12. Now n = 3(since we did factorial(n-1)). Then we check is n == 0? No, so we execute the else statement where n * n -1 and add it to 12. We keep repeating this until the if statement is executed and n == 0. I have only just understood this myself, so it may not be correct, but that's my take on it.


#8

Several instances of the factorial function can be in the process of execution at the same time, each with its own variable, n.

Let's assume that we have the following function call ...

print(factorial(4))

An instance of factorial begins execution with n equal to 4. Without terminating its own execution, that instance of factorial makes the call, factorial(3), so that it can complete its calculation needed for this statement ...

return n * factorial(n - 1)

Now, there are two instances of factorial executing, one of them with n equal to 4, and the second with n equal to 3.

Additional calls are made, down the line, until finally there is an instance of factorial where n is equal to 0. Thus far, all instances of factorial, each with its own n, are executing, with none of them having terminated.

Now that final instance, representing the base case where n is equal to 0, can terminate its execution and return its result of 1 to the instance in which n is equal to 1.

The instance of factorial where n is equal to 1 can now use the value of 1 that got returned from the base case to complete this calculation ...

return n * factorial(n-1)

..., and it returns its result of 1 to the instance where n is equal to 2. That instance returns its result of 2 to the instance that has n equal to 3. That instance returns 6 to the original instance invoked by factorial(4). Finally, that instance returns 24, which is printed.

The diagram below, from GitBook: Subsets of Algorithms and Data Structures, and More: Recursion, illustrates the process.


#9

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