razzdango razzdango - 3 years ago 76
Python Question

Trouble returning in recursive call

I have successfully completed and passed a project for a course I am taking where I create all possible 4 letter password combinations for cracking a DES hash. When I find a match, it should return immediately but I know that my function is poorly designed. I understand basic recursion but I have always had trouble understanding it for any useful purposes. In this case I found that the only way I could make the method return is by checking a password variable initialized in the encapsulating function along with the nonlocal attribute.

I had this working without nonlocal before I came to my final solution, but it would continue for a while without returning anything even though it correctly printed out the password when found.

How can I correctly use recursion to return the correct password by propagating the value up correctly? Thank you for any help or tips that you can provide!

def brute_force_crack(hashed_pass):
char_list = create_possible_chars()

# Store all string combinations
password = ""

# Build the combos adding each letter to each prefix and then to combos.
def build_combos(curr_str):

nonlocal password

# Check password to return early
if password != "":
return
if len(curr_str) == 4:
return

for letter in char_list:
# Add letter to curr_str to build up the combo
curr_str += letter

if is_password(curr_str, hashed_pass):
password = curr_str
break

build_combos(curr_str)
# Reset curr_str to be used again in this iteration without the added letter
curr_str = curr_str[:-1]

build_combos("")
return password

Answer Source

You should aim to let the recursive function return the correct password when found, instead of setting a non local variable.

Secondly, perform the password check at the start of the recursive function, at the same time you check for failure. This may seem overkill the first time (as an empty string will not match), but it is cleaner code.

Here is how it could look:

def brute_force_crack(hashed_pass):
    char_list = create_possible_chars()

    # Build the combos adding each letter to each prefix and then to combos.
    def build_combos(curr_str):
        # Check for success
        if is_password(curr_str, hashed_pass):
            # Return the match
            return curr_str
        # Check for failure
        if len(curr_str) >= 4:
            return

        for letter in char_list:
            # Add letter via argument to build up the combo
            password = build_combos(curr_str + letter)
            # If a result is returned, we can quit
            if password:
                return password

    # Return whatever is returned recursively
    return build_combos("")
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download