파이썬의 반복과 재귀

상황이 발생하면 재귀 연산이 필요하지만 재귀 횟수가 10,000회가 넘을 정도로 매우 많습니다. 10,000회 이상의 재귀에 대해서는 이야기하지 않겠습니다. 원본 테스트 코드는 java에 있습니다. jdk와 컴파일 환경이 없으면 Python을 사용하겠습니다.

먼저 원본 Java 코드를 살펴보겠습니다.

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));
    }
}

Java를 많이 다루지는 않았지만 이 코드 줄은 여전히 ​​스트레스가 없습니다. 빠르게 정리하고 Python 코드로 변경했습니다

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

코드 붙여넣기, F5, 뭔가 잘못되었습니다

이 버전의 코드는 원래 길게 추가되지 않았습니다. -숫자 정수를 직접 사용하는 경우도 있기 때문에 long과 관련이 있는지 의심스럽습니다

물론 실제로는 Python에서 지원하는 정수 길이가 매우 깁니다. 이전에 작성된 코드를 참조하세요.

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

위 코드는 긴 10진수 문자열을 16진수 표현으로 변환하거나 임의의 16진수로 변환할 수 있습니다. 시스템이나 16진수 8진수 시스템으로 그리고 16진수는 그냥 oct(), hex()를 이용해서 풀고, 유클리드 나눗셈을 이용해서 풀면 된다

그러므로 에러가 거짓말을 하지 않는다고 볼 수 있다 숫자의 크기로 따지면 결국 11589가 있군요. 컴퓨터로는 그냥 반찬일 뿐이고 2^16과 65536도 있습니다

사실 진짜 이유는 여기서야 알았습니다. 이전 재귀 오류는 언급도 안하고 초췌했어요

재귀 오류가 발생한 이유는 파이썬 때문이었습니다. 기본 재귀 제한은 1000회 정도밖에 안 되는데 여기서는 10000회 이상을 실행해야 해서 오래 걸렸습니다. 시간 브러싱: RuntimeError: 최대 재귀 깊이 초과

그래서 재빨리 확인해 보니 재귀 제한을 직접 설정할 수 있습니다. 최대 재귀 횟수는 확장으로 확인할 수도 있습니다. 공식 홈페이지 문서

일반적으로 Python 언어에서는 기본적으로 이점과 충돌을 방지하기 위해 횟수 제한을 추가하는데 이 제한을 변경하면 괜찮을까요?

import sys

# 최대 깊이를 20000으로 설정

sys.setrecursionlimit(20000)

위 코드를 삽입하고 이제 단호하게 20000으로 변경합니다. , 문제가 없어야 하는데 결과가 충격적이었습니다. 아무것도 출력되지 않았습니다.

계속 확인하지 않고 친구 littlehann에게 문의했지만 이 문제에 대해 자세히 알아보지 않았습니다. 내려가세요. 그러나 실제 응용 프로그램에서 재귀 연산의 효율성에 관해서는 교과서를 제외하고는 반복을 사용하는 경우가 거의 없습니다. 그다지 인상적이지는 않지만 for 문을 사용하면 이를 처리할 수 있습니다

코드는 다음과 같습니다.

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

코드 몇 줄만으로 단숨에 완성되었습니다. 지난 인터뷰를 생각하면서 tx 면접관이 알고리즘에 대해 물었을 때 재귀를 사용하여 연산을 구현한다고 언급했습니다. 이제 Iteration도 사용할 수 있습니까?

시간이 오래 걸려 당시 질문을 명확하게 기억할 수 없지만, 오늘의 교훈은 대부분의 경우(작성된 코드 적음, 느낌에 따라 추정) 재귀적 효율성입니다. 상대적으로 낮다는 건

수업에서도 언급한 게 확실해요. 반복을 사용하는 것의 효율성은 분명히 재귀보다 높습니다(반복의 구체적인 개념은 명확하게 기억나지 않습니다). 적어도 수십만 번의 연산을 수행하더라도 문제가 없을 것이라고 확신합니다. 재귀 제한을 변경했는데 여전히 파업이 발생했습니다

마지막으로 python long VS C long long 링크를 게시하여 관심이 있으시면 확인하실 수 있습니다