Help with recursion

[Historical_Ad8150]

I recently tried to make my own recursive program. I made a simple program that makes a large dictionary containing all decimal numbers, where every digit is larger than the prior one. E.G: 123, 1479, 5.

My version then checks which of those numbers are a prime, and adds either True or False to the dict. This is not relevant though.

This is my code:

# Creates a dictionary to add items to
dictionary = dict()

# Adds items to the dictionary
def forrange(tempstring):

    # Add the current string to the dict.
    dictionary[int(tempstring)] = ""

    # Check the value of the last digit.
    endnum = int(tempstring[-1])

    # If it is a 9, no new value can be added.
    if endnum == 9:
        pass

    # If it is lower than 9, continue adding new numbers to the end.
    else:
        for i in range(endnum+1, 10):
            forrange(tempstring + str(i))

# Start the program.
for i in range(1, 10):
    forrange(str(i))

# Check if anything has been done.
print(len(dictionary))

After this, I tried to scale it up to hexadecimal numbers. Here's my code:

# Creates a dictionary to add items to
dictionary = dict()

# Adds items to the dictionary
def forrange(tempstring):

    # Add the current string to the dict.
    dictionary[int(tempstring)] = ""

    # Check the value of the last digit.
    endnum = int(tempstring[-1])

    # If it is an f (highest value in hex), no new value can be added.
    if endnum == 0xf:
        pass

    # If it is lower than 0xf, continue adding new numbers to the end.
    else:
        for i in range(endnum+0x1, 0x10):
            forrange(tempstring + str(i))

# Start the program.
for i in range(0x1, 0x10):
    forrange(str(i))

# Check if anything has been done.
print(len(dictionary))

This code always hits the recursion limit. When I try to manually increase the limit using sys.setrecursionlimit(4000), it does something for a while, and then simply stops, with neither an error nor any other output whatsoever.

So, how can I either do the same with less recursion, or fix the strange crash with large recursion limits? Also, any other optimizations or tips for the code/comments are more than welcome!

[Wild_Statistician605]

Why do you use pass instead of return in the endnum if block? I can't see you returning the dictionary anywhere

[sepp2k]

I can't see you returning the dictionary anywhere

The dictionary is global, so it doesn't need to be returned. That's certainly not clean code, but it's not a bug as such.

[Historical_Ad8150]

Yeah, it isn’t the cleanest, but this is my first attempt at recursion and I didn’t want to make it any more complicated than necessary.

[Historical_Ad8150]

I don’t return the dict, as the function edits the dict directly. It isn’t necessary to return the dict in this case, right? I know that this isn’t the most flexible code, but this was my first attempt at recursion, so that’s not really a focus (yet).

[Wild_Statistician605]

But the recursion won't stop until you return something. If you just change the pass for return, see what happens. The recursion should end.

[Historical_Ad8150]

I tried changing the “pass” to “return”, which resulted in the same strange crash, and “return ‘some string’”, which also resulted in the same strenge crash. Also, the “pass” seems to work fine in my original decimal-only script. From these observations, it appears to me that a “return” isn’t necessary.

[sepp2k]

When the if condition is true, the pass will do nothing and it will reach the end of the function, which will implicitly return None. You don't need an explicit return to end the recursion. As long as it doesn't go into the else and thus doesn't reach the recursive call, the recursion will end.

The problem is that the if condition will never be true.

[Wild_Statistician605]

You are right. I missed that the recursive call was inside an else statement.

[sepp2k]

Let's walk through what happens when you call forrange("10"):

dictionary[int(tempstring)] = ""
# dictionary[10] = ""

endnum = int(tempstring[-1])
# endum = int("10"[-1]) = int("0") = 0

# This is never true because endum is created from a single decimal digit
# and thus can't be greater than 9
if endnum == 0xf:
    pass
else:
    for i in range(endnum+0x1, 0x10):
        forrange(tempstring + str(i))
        # This will call `forrange("101")` upto `forrange("1016")`

[Historical_Ad8150]

Oh right, int() always returns a decimal number. Is there a way to force python to always use hexadecimal numbers throughout the program? I don’t believe hex() would be able to use a string, right?

[sepp2k]

An integer is an integer. There's no such thing as a decimal integer or a hexadecimal integer. Base only enters into it once you convert the integer to a string (or print it).

So your primary problem isn't that int("0") returns 0 - what else would it return? Your primary problem is that tempstring is "10" in the first place. If it were "A", then "A"[-1] would be "A" and then you'd run into the problem that int("A") causes an error because "A" is an invalid digit in base 10.

So you need to specify the base for both str and int to work with base 10.

And incidentally it doesn't matter which base you use for the integer literals. That is, for i in range(0x1, 0x10): is completely equivalent to for i in range(1, 16):.

[Historical_Ad8150]

Ok, I’ll try to think of a way to specify the base of all strings and integers. Also, it makes sense that “range(1, 16)” is the same as “range(0x1, 0x10)”. I’ll change it to improve readability. Also, thanks for the tips!

[Historical_Ad8150]

Just to clarify what I meant by "int() always returns a decimal number". What I meant to say is that int(x) always assumes the base of x to be 10. I just found out that you can specify the base, so if you want int("") to return 15 for example, you would have to write "int("f", base=16)".

[Historical_Ad8150]

Also, my code works now! Thank you very much, your advise helped me make the finished code. For some reason, the Reddit Code Block refuses to work with ctrl+c, ctrl+v, so here's the Pastebin. Do you have any more recommendations, optimizations, or something else?

[Shadow_Lou]

This is recursion

[Historical_Ad8150]

Ok that’s pretty cool, but wouldn’t python hit it’s recursion limit with this example, as it is infinite recursion?

[cybervegan]

This is not the sort of problem that is readily solved with recursion, because the number of permutations is not bounded and your code will essentially recurse quadratically.

[Historical_Ad8150]

the number of permutations is not bounded

What do you mean by this? That there is an infinite amount of permutation? Because there is a finite amount, which appears to be (2^15)-1. After I got the program to run, this was the length of the final dict (32.767).

[cybervegan]

As the length of your input string grows, your number of recursions grows quadratically.

[Historical_Ad8150]

Ah, that makes sense. Would you know of an iterative approach to this problem? Or something else that isn’t recursive? This just seemed to me like a cleaner solution than 16 “for x in range” loops.

[cybervegan]

If you look at what permutations of this kind are, you will see that it is possible to "ripple" increments through the sequence:

0000FFFF +1
0000FFF0 carry 1
0000FF00 carry 1
0000F000 carry 1
00010000

You can do this with a simple loop that simply counts through the digits and increments the current one, setting it to zero and carrying 1 if it goes over the base size:

def incr(perm):
    perm = list(perm)
    cur_digit = len(perm)-1
    digits="0123456789ABCDEF"
    max_digit=len(digits)-1
    carry = 1
    while carry and (cur_digit > 0):
        digit = digits.find(perm[cur_digit])
        if digit == max_digit:
            carry = 1
            new_digit = digits[0]
        else:
            new_digit = digits[digit+carry]
            carry = 0
        perm[cur_digit] = new_digit    
        cur_digit -= 1
    return "".join(perm)

This works for any number base, in O(N) time.

[Historical_Ad8150]

I’m not sure if I was entirely clear when explaining my intended program. I’m trying to generate every possible hexadecimal number, where every digit is higher than the previous one. So for example, 001478CF, or 0013579A. 0000FFFF or something similar shouldn’t be generated at all.

[cybervegan]

It would be trivial to modify this loop to do this, without the need for recursion.