Detailed explanation of iteration and recursion methods in python

When encountering a situation, it is necessary to perform a recursive operation, but the number of recursions is very large, more than 10,000 times. Let’s not talk about more than 10,000 recursions. The original test code is in java. Without jdk and compilation environment installed, 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 are still not stressful. I cut the mess quickly and changed 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

Stick the code, F5, something went wrong

This version of the code originally did not add long, because the previous string of more than ten digits integers can be used directly, so I suspect it has something to do with long

Of course, in fact, this has nothing to do with long. The integer length supported by Python is very long. Refer to the code written before:

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

The above code will convert a long string of Decimal numbers can be converted to hexadecimal representation, or to any hexadecimal system, or to octal and hexadecimal. Just use oct() and hex() to solve the problem. Use euclidean division to solve the problem.

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. There are 2^16 and 65536.

In fact, I didn't find out until here that there is no Talking about the real reason for the previous recursive error, I am 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

General To put it bluntly, in order to prevent benefits and crashes, 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 and decisively change it to 20000. Now there should be no problem without this limit, but the result is shocking , nothing was output, I was confused

and did not continue to check. I asked my friend littlehann and discussed it, but did not delve into this issue further. 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 of

is just to evaluate. I didn’t want to study it in depth, so I decided to use it instead. Let's iterate, although I'm not very impressed, but it can be done with a for statement

The code is as follows:

def calc(depth):
    tmp = 0
    result = 1
    
    for i in xrange(0,depth+1):
        cc = result
        if (cc ^ i)%4 == 0:
            tmp = 1
        else:
            tmp = 0
        result = result + (i)%7 + tmp
        
    return result
final = calc(11589)
print final

In just a few lines of code, it was done in one go . 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 questions clearly at that time, but today’s lesson is: in most cases (less code written, estimates based on feelings), recursive The efficiency is relatively low, this can be determined, and it was also mentioned in 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 loop. I am sure that there will be no problem with hundreds of thousands of operations, but even if I change the recursion limit, 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

The above is the detailed content of Detailed explanation of iteration and recursion methods in python. For more information, please follow other related articles on the PHP Chinese website!