Jump to content
  • Advertisement
Sign in to follow this  
random_thinker

Python beginner...there's no such thing as a stupid question?

This topic is 3883 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Just started playing with Python, when reading 'Core Python Programming' I came across this example:
#!/usr/bin/env python

import sys,string

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

def main(argv):
    print factorial(string.atoi(argv[1]))

if __name__ == "__main__":
    main(sys.argv)
I don't understand why this does not exit always with answer 1, as the argument 'n' is going to be reduced by 1 at each recursion. Is there something going on in Python with static behaviour or something else going on? Could I have some help understanding how the stack unwinds? random_thinker

Share this post


Link to post
Share on other sites
Advertisement
Its using recursion to do the calculation. if you are unsure of this do a google search. The best way to understand small functions like this is to take a piece of paper and write down the flow of execution. I'm sure after writing a few lines you will get how it works

Share this post


Link to post
Share on other sites
Let's say you call the function with value 3, the function will return 3*factorial(2). factorial(2) will return 2*factorial(1), and factorial(1) will return 1. Now, since factorial(1) is 1, factorial(2) will return 2*1. Since factorial(2) is 2*1, factorial(3) will return 3*2*1.

Share this post


Link to post
Share on other sites
Hmm... that's the "canonical" form of a factorial function which works in *any* language that supports recursion. Let's unwind the recursive call and see what it looks like. For every f(k), we're substituting k*f(k-1), as per the definition:


f(n)
= n * f(n-1)
= n * ( (n-1) * f((n-1)-1) )
= n * ( (n-1) * ( (n-1-1) * f((n-1-1)-1) ) )
= n * ( (n-1) * ( (n-1-1) * ( (n-1-1-1) * f((n-1-1-1)-1) ) ) )
= ...
= n * (n-1) * (n-1-1) * ... * f(n-(n-1))
= n * (n-1) * (n-1-1) * ... * 1
= n!

Share this post


Link to post
Share on other sites
As you seem to have noticed, factorial is a recursive function; that is, a function which calls itself. To understand what it does, you must nest multiple calls. Always start with the outer one - the one called from main(). For this example, let's say that you gave the argument of 4 to the program.

We start with factorial(4). Does 4 equal 1 or 0? No, so we return 4 * factorial(4-1). This reduces to 4 * factorial(3). Does 3 equal 1 or 0? No, so we return 3 * factorial(3-1). In total we now have 4 * 3 * factorial(2). It is important to note that when we calculated facotrial(3), the "4 * " part did not just disappear. It is still there. Now we continual with factorial(2). 2 doesn't equal 1 or 0, so return 2 * factorial(1). This gives us 4 * 3 * 2 * factorial(1). 1 equals one, so facotrial(1) returns merely 1. In total we now have 4 * 3 * 2 * 1. Which equals 24. Mission successful!

Notice how each call to factorial() is nested inside of a previous call, but has more stuff tacked onto it. It may be easier to see this by writing the end result like so:

(4 * (3 * (2 * 1) ) )

Edit: Beaten! Four times! Oh well.

Share this post


Link to post
Share on other sites
Wow! Thanks. My confusion stemmed from Python and the 'return' keyword. In this case, it seems that on the last recursion, 'return 1' returns to the 'return ( n * factorial(n-1))' where 'factorial(n-1)' is replaced by 1. Am I wrong in thinking that in some other languages the 'return' statement operates like 'break', where the function is simply exited?

random

Share this post


Link to post
Share on other sites
Return always "breaks" out of the function.

In this case there are many times the function is called over and over. It keeps calling itself until it hits the base case, then it returns. Then THAT "instance" of the function returns, then it goes to the function that was called before it, which was ITSELF. [grin]

Share this post


Link to post
Share on other sites
Return in any language I know of returns from the current function call. That is, if I have a function

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

The underlined expression is a recursive function call. What happens inside that call does not depend on where it was called from (at least not until you start playing around with exceptions). In other words, you cannot return from a function, only from the current call (/invocation).

Share this post


Link to post
Share on other sites
Yes, so...reading about Python, I cannot decide whether it is procedural, functional or object oriented. It seems to offer all three.

In the above case though, what is shown is a recursion within a procedural context, so 'return' simply goes back to where it was called from. In this instance, the last call returns 1 to the 'return ( n * factorial(n-1))' and this returns to 'print <>' and then exits. Is that right? Thanks all for helping me gain a clearer understanding of this Python beginner stuff.

--random

Share this post


Link to post
Share on other sites
Quote:
Original post by random_thinker
In the above case though, what is shown is a recursion within a procedural context, so 'return' simply goes back to where it was called from.

Not sure what you mean. Recursion is pretty much the same everywhere, and 'return' always returns to where the function was called from.

That's why it's called return. That's what the word means. Going back to where you were before.

Of course, in recursive functions, "where you were before" might well be inside the same function. So you return to there. And when that returns, you might return to the same function again. And sooner or later, you'll get out to where the function was first called from.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!