[Ntwiles]

Hey guys. I'm trying to learn Python because apparently I have programming language ADD. I'm having trouble with this program:

def getUsername(errornum):
    if errornum == 0: 
        username = raw_input("Please enter a username: ")
        error = checkUsername(username)
        if error == 0: return username
        else: getUsername(error)
    if errornum == 1:
        print("You must enter a username.")
        getUsername(0)

def checkUsername(username):
    if username == "":
        return 1
    else: return 0
 

print("Welcome!")
username = getUsername(0)
print("Your username is "+str(username)+".")

When I enter a username, it prints it fine. But if I enter no username, then enter one after the error message is shown, it prints "Your username is None", instead of the one I entered. I'm wondering if this is because I'm having a function calling itself and its losing the return value somehow? Thanks

This post has been edited by Ntwiles: 13 December 2010 - 06:00 PM

[Martyr2]

Well it is because you are using recursion here. When you enter no value, you get error set to 1 which then ends up calling getUsername(0) again where it reprompts. All fine so far. But when you then enter a value, it has an error of zero, so it returns the name... but to where? To the previous getUsername call right? But then you don't return it there again. Get what I am saying?

If you call the function within itself, when one of the "inner calls" complete it comes back to the call that had called it. Then it finishes and again returns to the getUsername call that called it etc until it "unwinds".

Think of a folder hierarchy. When you go into a sub directory, and then down into a sub directory of that, when you return from that you go to the sub directory that was the "parent" and then when you return from that it go back to the parent of that folder.

GetUsername1
  |___ GetUserName2
           |__ GetUserName3

GetUsername1 calls 2 which calls 3... when 3 finishes it goes back to 2 which returns to 1. So to fix this we need return statements where ever we call getUserName

def getUsername(errornum):
    if errornum == 0: 
        username = raw_input("Please enter a username: ")
        error = checkUsername(username)
        if error == 0: return username
        else: return getUsername(error)
    if errornum == 1:
        print("You must enter a username.")
        return getUsername(0)

def checkUsername(username):
    if username == "":
        return 1
    else: return 0
 

print("Welcome!")
username = getUsername(0)
print("Your username is "+str(username)+".")

It is called "unwinding the call stack" and it is what happens after you return up the call stack after hitting the "base case".

[Ntwiles]

Aha, thanks for the help. I just confused myself with all the looping around. Recursion definitely looks like something to be careful with. Is it usually considered a good method to use?

[Martyr2]

Oh it is certainly good to use for SOME problems. How you are using it is not exactly the best application of it. You can use a simple loop to do what you are doing. But you can write any recursive solution into a loop. Use recursion sparingly and make sure the problem really warrants it. Recursion for a quick sort for instance is a good application, a recursive solution for fibonacci is not. (Despite what some people say that it is a good use it is really not since it can accrue a costly overhead of function calls).



P.S. First step to prevent problems with recursion... think about the "base case" first. What condition needs to be met to stop the recursion. Once you identify this, then code outwards from there.

This post has been edited by Martyr2: 13 December 2010 - 07:25 PM

[atraub]

Recursion is a touchy subject. I've met some people who say you should never ever use it. I love the topic mainly because it is so controversial!

I personally like recursion. It often leads to shorter cleaner code when used appropriately. I would suggest not using recursion if you knew that the "recursion depth" would be fairly substantial. Sometimes, in VERY rare scenarios, recursion can prove slightly more efficient than loops. One such scenario is this:

Imagine a scenario where you can use a while loop or recursion in the event that a certain condition has been met. Another KEY aspect of this scenario is that this condition being met is a RARITY. My definition of Rare is less than 5% (in testing I used approximately 2.5%). In this situation a recursion would be seldom, but your program would have to go through the overhead of making a loop every single run through regardless. Still think looping will be more efficient? I can't blame you. To some, the idea of recursion EVER being superior is laughable. Here's a script I created to demonstrate one such situation:

"""
Recursion test
A proof of concept program used to demonstrate that recursion can be
more efficient than looping in some scenarios.

atraub
12/14/2010
"""
import time
import random

#Records the elapsed time during testing
def test(numList, theFunction): 
    start = time.time() 
    for item in numList:
        theFunction.__call__(item)
    end = time.time() 
    return end - start #elapsed time in seconds

#in a rare scenario, do some substantial math then loop
def iterativeFunction(num):
        while num <= 5:
            x = num**25
            num += 3
        return num

#in a rare scenario, do some substantial math then make a recursive call
def recursiveFunction(num):
    if num <= 5:
        x= num **25
        return recursiveFunction(num+3)
    return num


#Create 'count' numbers between low and high and return a list holding them
def createNumList(count=100000, low=1, high=200):
    numList = []
    for i in range(count):
        numList.append(random.randint(low,high))
    return numList

def main(testCount=20):
    recurTime = []
    iteraTime = []
    for i in range(testCount):
        x = createNumList()
        recurTime.append(test(x,recursiveFunction))
        iteraTime.append(test(x,iterativeFunction))
    print("Average speed with Recursion: ",sum(recurTime)/len(recurTime))
    print("Average speed with iteration: ",sum(iteraTime)/len(iteraTime))

After running main 10 times, here are my results: (code tags improved formatting)

#Lower is better!

Average speed with Recursion:  0.0384999752045
Average speed with iteration:  0.0417500257492

Average speed with Recursion:  0.0381500005722
Average speed with iteration:  0.0425000071526

Average speed with Recursion:  0.0393000006676
Average speed with iteration:  0.0420499801636

Average speed with Recursion:  0.0383500218391
Average speed with iteration:  0.0412500023842

Average speed with Recursion:  0.0388500094414
Average speed with iteration:  0.0419499993324

Average speed with Recursion:  0.0385499835014
Average speed with iteration:  0.0418499827385

Average speed with Recursion:  0.0391000032425
Average speed with iteration:  0.0417500257492

Average speed with Recursion:  0.0378999710083
Average speed with iteration:  0.0422000169754

Average speed with Recursion:  0.0381500244141
Average speed with iteration:  0.0426000118256

Average speed with Recursion:  0.0392000079155
Average speed with iteration:  0.0418500661850

As you can see, scenarios do exist where recursion is more efficient, albeit they are rare.

This post has been edited by atraub: 14 December 2010 - 07:20 AM