Python : print 1-1000000 with recursion-CodePudding

This code results in RecursionError: maximum recursion depth exceeded while calling a Python object . I know it is very easy to use loop but is there any way to implement it using recursion without increasing recursion limit? Tail call optimization is one method? Are there any other methods?

def print_recursion(m,n):
    if m==n:
        return
    else:
        print_recursion(m 1,n)

print_recursion(1,1000000)

CodePudding user response：

You can use a divide and conquer strategy. Treat the problem like in-order traversal of a binary tree where conceptually each node contains a range. The root contains the full range, and each descendent node contains half the range of its parent. You print the current value when the lower_limit of the range equals the upper_limit. Otherwise, calculate the midpoint of the range and make two recursive calls to the subranges (lower_limit, midpoint) and (midpoint 1, upper_limit). This cuts the problem in half at each level of the recursion, so the recursive stack size is O(log(N)) where N is the original range length. For a range of 1_000_000 the tree's height is 20.

The code is:

def print_recursion(lower_limit, upper_limit):
    if lower_limit == upper_limit:
        print(lower_limit)
    else:
        midpoint = lower_limit   (upper_limit - lower_limit) // 2
        print_recursion(lower_limit, midpoint)
        print_recursion(midpoint   1, upper_limit)

print_recursion(1, 1000000)

I tested it with smaller ranges to confirm it works as it should, then ran a timing for the full range:

% time python3 rec.py | wc       
 1000000 1000000 6888896
python3 rec.py  0.32s user 0.01s system 95% cpu 0.343 total
wc  0.01s user 0.00s system 4% cpu 0.333 total
%

As you can see, the Python portion of this runs in about 1/3 of a second. This is using Python 3.10.8 on M1 MacBook Pro. Word count (wc) confirms that there were a million lines.

In practice you should just do this with a loop as Samwise said in their comment, but if you insist on recursion and are dealing with large ranges this approach is simple, readable, and maintainable in my opinion.