Iteration and recursion in python

Encountered a situation where a recursive operation was required, but the number of recursions was very large, more than 10,000 times. Let’s not talk about more than 10,000 recursions. The original test code is in Java. There is no jdk or compilation environment installed, so let’s use Python. Let’s take a look at the original Java code first:

public class UpCount {
    private long calc(int depth) {
        if (depth == 0) return 1;
        long cc = calc(depth - 1);
        return cc + (depth % 7) + ((((cc ^ depth) % 4) == 0) ? 1 : 0); 
    }
    public static void main(String[] args) {
        UpCount uc = new UpCount();
        System.out.println(uc.calc(11589));
    }
}

I haven’t played much with java. , but these lines of code seem to be stress-free, so I cut the mess quickly and changed it to python code

def calc(depth):
    if depth == 0:
        return 1
    cc = long(calc(depth-1))
    xor_mod = (cc ^ depth)%4
    if xor_mod == 0:
        return cc+(depth%7)+1
    else:
        return cc+(depth%7)
  
number = long(calc(11589))
print number

The code is pasted, F5, something went wrong

This version of the code originally did not add long. Because a string of more than ten digit integers can be used directly, so I doubt it has something to do with long. Of course, in fact, it has nothing to do with long. The length of integers supported by python is very long. Please refer to what I wrote before The code of Just use oct() and hex() to solve it. Let’s use euclidean division to solve it

Therefore, it can be seen that the error does not lie in the size of the number. After all, 11589 is just a piece of cake for today’s computers, and 2^16 and 65536

In fact, I only found out here that the real reason for the previous recursive error was not mentioned. I was haggard

The reason for the recursive error is because the default recursion limit of python is only about 1000 times, but here it has to run 10000+, and it took a long time to refresh : RuntimeError: maximum recursion depth exceeded

So I checked it quickly and found that I can set the limit of recursion myself. See the maximum number of recursions in python. As an extension, you can also check the official website documentation

In general, in order to prevent the benefits and Crash, the python language adds a limit to the number of times by default, so if I change this limit, will it be ok?

import sys

# set the maximun depth as 20000

sys.setrecursionlimit(20000)

Insert the above code, I decisively changed it to 20000. Now there should be no problem without this restriction, but the result was shocking. Nothing was output. I was confused. I didn’t continue to check. I asked my friend littlehann and discussed it. There was no response to this. Let’s delve deeper into the issue. But when it comes to the efficiency of recursive operations in practical applications, it is indeed rare to see the use of recursion except in textbooks

The original purpose is just to evaluate, I don’t want to study it in depth, let’s use iteration instead, although I’m not very impressed, but a for statement can handle it. The code is as follows:

cimal = 7
original = 28679718602997181072337614380936720482949
array = ""
result= ""
while original !=0:
    remainder = original % cimal
    array += str(remainder)
    original /= cimal
length = len(array)
for i in xrange(0,length):
    result += array[length-1-i]
print result

With just a few lines of code, it’s done in no time. Thinking of the last interview, the interviewer from tx asked me about the algorithm. At that time, he mentioned using recursion to implement an operation. Then I thought about it, can it also be used iteration?

It’s been a long time, and I can’t remember the question clearly at that time, but today’s lesson is: in most cases (less code written, estimate based on feeling), the efficiency of recursion is relatively low. This is certain, it was also mentioned during class

. The efficiency of using iteration is obviously higher than that of recursion (I don’t remember the specific concept of iteration clearly). At least use loops. I am sure that there will be no problem if it is calculated hundreds of thousands of times. But even if I changed the recursion limit, I still encountered a strike

Finally, I will post a link to python long VS C long long. If you are interested, you can check it out