Why does this iterative program exceed recursion limit?

Question

I'm trying to solve a project Euler question (number 52) which asks for the smallest integer, n, such that n, 2n, 3n, 4n, 5n, 6n all have the same decimal digits permuted. I thought I'd start with a brute force program (as a programming exercise for myself) which looks for an integer n such that n and 2n have the same digits (the project Euler question mentions that 125874 is one such integer, so I figured a brute force program would work). So I wrote a python program that looks at each integer in order, creates a sorted list of its digits, and compares that list against against the sorted list of digits for 2n. My program seems iterative, so I'm not sure why it stops running after a fraction of a second and sends back "maximum recursion depth exceeded in comparison". I decided to bound the unbounded search in the function "k" below to see how far it got, and it seems to have gotten no higher than n= 100,000. Given that each time it calls k, it only has to sort and compare two lists of size no more than 6, I wonder why it gives me this error? I googled the error and it was suggested to increase the recursion limit, so I added the "sys.setrecursionlimit(2000)" you see.

Here is my code:

The function f takes an integer and returns a list of its digits. g sorts them. h compares the list for n and 2n. and k iterates.

import math
import sys

sys.setrecursionlimit(2000)

def f(n, l):
    if (math.floor(n / 10) == 0):
        l.append(n)
        return l

    else:
        l.append(n % 10)
        return f(int((n - (n % 10)) / 10), l)

def g(n):
    return sorted(f(n, []))

def h(n):
    if ((g(n) == g(2 * n))):
        return 1
    else:
        return 0

def k(n):
    if ((h(n) == 1)):
        return n
    elif ((n <= 100000)):
        return k(n + 1)
    else:
        return "checked up to bound"

print(k(1))

`f` and `k` are definitely recursive, not iterative. True, it's a tail call, so *in theory* the compiler could optimize them to evaluate iteratively, [but Python doesn't do that](http://stackoverflow.com/q/13591970/744178). — jwodder, Dec 27 '16 at 00:33
@jwodder thanks for your help. but each time I call f, doesn't it just recurse 6 times if the size of n is no more than 100,000? — user7343674, Dec 27 '16 at 00:35
The traceback clearly shows that it's calling `k` over and over, so that's the problematic recursion. — Alex Hall, Dec 27 '16 at 00:38
By `if (math.floor(n / 10) == 0):`, did you mean `if -10 < n < 10:`? — TigerhawkT3, Dec 27 '16 at 00:39
Given as `k` is calling `k(n+1)` for n between 1 and 100000, that's not *at all* bounded to 6 times. Where/why do you think it's supposed to be bounded? — Charles Duffy, Dec 27 '16 at 00:39
It sounds like you might have gotten your concept of "iterative" from a course that misused the terminology. Your program has no loops in it. It is not iterative. Your functions call themselves. That's recursive. — user2357112, Dec 27 '16 at 00:42
@CharlesDuffy yeah I just meant f only recurses 6 times. thanks for your help. I'll have to think what's going on with k. — user7343674, Dec 27 '16 at 00:43
Thanks everyone. I definitely get it now. Apologies for the n00b question — user7343674, Dec 27 '16 at 00:51
@user2357112 My notion of iteration and recursion comes from the book "structure and interpretation of computer programs", which uses Scheme. Now that I revisit the chapter in that book, I see a note that says that Scheme is exceptional in that recursive programs are able to generate iterative processes. I guess maybe in Scheme, the analogue of the code I wrote would be iterative? — user7343674, Dec 27 '16 at 02:38
@user7343674: That book's use of "iterative process" and "recursive process" are highly unusual. — user2357112, Dec 27 '16 at 02:45

score 2 · Accepted Answer · answered Dec 27 '16 at 00:42

Focusing on this part:

def k(n):
    if ((h(n) == 1)):
        return n
    elif ((n <= 100000)):
        return k(n + 1)

125874 is the smallest number for which h(n) == 1, so this recursively calls k(1), k(2), k(3), ... k(125874). sys.setrecursionlimit(2000) cannot help with that. Go through the different values of n iteratively, i.e. with a loop.

Why does this iterative program exceed recursion limit?

1 Answers1