이 방법을 비 재귀 적으로 만드는 방법은 무엇입니까?

Question

안녕하세요. 이 예제는 매우 구체적이지만 광범위한 함수에 적용될 수 있다고 생각합니다. 온라인 프로그래밍 콘테스트에서 가져온 것입니다.

간단한 승리 조건의 게임이 있습니다. 끌기는 불가능합니다. 모든 움직임이 종결 상태에 더 가깝기 때문에 게임을 영원히 계속할 수 없습니다. 이 함수는 주어진 상태에서 현재 이동해야하는 플레이어가 승리 전략을 가지고 있는지 결정해야합니다. 예에서 상태는 정수입니다. 플레이어는 0이 아닌 숫자를 선택하고 숫자에서 숫자를 뺍니다. 새 상태가 새로운 정수입니다. 승자는 0에 도달 한 플레이어입니다. 나는 그것이 어떻게 작동하는지는 분명 생각

from Memoize import Memoize 

@Memoize 
def Game(x): 
    if x == 0: return True 
    for digit in str(x): 
     if digit != '0' and not Game(x-int(digit)): 
      return True 
    return False 

:

내가이 코딩. 나는 또한이 특정 게임을 위해 아마도 훨씬 똑똑한 해결책이 있다는 것을 알고 있지만 나의 질문은 일반적이다. 그러나 이것은 상대적으로 작은 입력에 대해서조차도 파이썬을 미쳤습니다. 이 코드가 루프에서 작동하도록하는 방법이 있습니까?

감사

이 내가 루프로 번역 무엇을 의미하는 것입니다 : "미쳐"으로

def fac(x): 
    if x <= 1: return x 
    else: return x*fac(x-1) 

def fac_loop(x): 
    result = 1 
    for i in xrange(1,x+1): 
     result *= i 
    return result 

## dont try: fac(10000) 
print fac_loop(10000) % 100 ## works 

Answer 1

일반적으로 재귀 함수가 primitive-recursive 인 경우에만 루프로 변환 할 수 있습니다. 이것은 기본적으로 그들이 한 번만 몸속에서 자신을 부른다는 것을 의미합니다. 함수는 자신을 여러 번 호출합니다. 이러한 함수에는 실제로 스택이 필요합니다. 스택을 명시 적으로 만들 수 있습니다 (예 : 목록과. 명시 적 스택을 사용하여 알고리즘을 다시 정의하면 다음과 같습니다.

def Game(x): 
    # x, str(x), position 
    stack = [(x,str(x),0)] 
    # return value 
    res = None 

    while stack: 
     if res is not None: 
      # we have a return value 
      if not res: 
       stack.pop() 
       res = True 
       continue 
      # res is True, continue to search 
      res = None 
     x, s, pos = stack.pop() 
     if x == 0: 
      res = True 
      continue 
     if pos == len(s): 
      # end of loop, return False 
      res = False 
      continue 
     stack.append((x,s,pos+1)) 
     digit = s[pos] 
     if digit == '0': 
      continue 
     x -= int(digit) 
     # recurse, starting with position 0 
     stack.append((x,str(x),0)) 

    return res 

기본적으로 각 로컬 변수를 스택 프레임의 요소로 만들어야합니다. 여기서 로컬 변수는 x, str (x), 루프의 반복 카운터입니다. 반환 값을하는 것은 약간 까다 롭습니다. 함수가 방금 반환 된 경우 res를 None으로 설정했습니다.

Answer 2

난 당신 말은 가정

이

>>> Game(10000) 
# stuff skipped 
RuntimeError: maximum recursion depth exceeded in cmp 

당신은 하단에 시작할 수 대신에 원한 변화는 다음과 같습니다 :

# after defining Game() 
for i in range(10000): 
    Game(i) 

# Now this will work: 
print Game(10000) 

높은 숫자로 시작하면 바닥 글 (0)에 도달하기 전에 먼 길을 재귀해야하므로 메모 장식자가 도움이되지 않습니다.

아래부터 시작하면 모든 재귀 호출이 결과 사전에 즉시 도달한다는 것을 확인할 수 있습니다. 아마도 여분의 공간을 사용하지만 멀리 재연하지 마십시오.

기본적으로 호출 스택을 수동으로 실행하는 루프 및 스택을 사용하여 모든 재귀 함수를 반복 함수로 설정할 수 있습니다. 예를 들어, 어떤 토론을 위해 this question 또는 this quesstion을 참조하십시오. 여기에는 좀 더 우아한 루프 기반 솔루션이있을 수 있지만 나에게로 뛰지는 않습니다.

Answer 3

재귀는 주로 이전 컨텍스트와 순서를 잃지 않고 일부 코드를 실행할 수 있다는 것입니다. 특히, 함수 프레임은 재귀 중에 호출 스택에 저장되고 저장되므로 스택 크기가 제한되어 있기 때문에 재귀 깊이에 제한이 있습니다. 힙 메모리에 상태 스택을 만들어 각 재귀 호출에서 필요한 정보를 수동으로 관리/저장하여 재귀 깊이를 '증가'시킬 수 있습니다.일반적으로 사용 가능한 힙 메모리의 양은 스택의 양보다 큽니다. 좋은 빠른 정렬 구현은 끊임없이 변화하는 상태 변수 (하위/상위 배열 경계 및 QS 예에서 피벗)가있는 외부 루프를 생성하여 더 큰 측면에 대한 재귀를 제거합니다.

필자가 이것을 입력하는 동안 Martin v. Lwis는 재귀 함수를 루프로 변환하는 것에 대한 좋은 대답을 게시했습니다.

Answer 4

당신은 당신의 재귀 버전을 약간 수정할 수 :

def Game(x): 
    if x == 0: return True 
    s = set(digit for digit in str(x) if digit != '0') 
    return any(not Game(x-int(digit)) for digit in s) 

이렇게하면 자리를 여러 번 검사하지 않습니다. 예를 들어, 111 세를하면 110 번을 세 번 볼 필요가 없습니다. 그것은 첫번째 X 숫자의 집합을 계산

import Queue 
def Game2(x): 
    memo = {} 
    memo[0] = True 
    calc_dep = {} 
    must_calc = Queue.Queue() 
    must_calc.put(x) 
    while not must_calc.empty(): 
     n = must_calc.get() 
     if n and n not in calc_dep: 
      s = set(int(c) for c in str(n) if c != '0') 
      elems = [n - digit for digit in s] 
      calc_dep[n] = elems 
      for new_elem in elems: 
       if new_elem not in calc_dep: 
        must_calc.put(new_elem) 
    for k in sorted(calc_dep.keys()): 
     v = calc_dep[k] 
     #print k, v 
     memo[k] = any(not memo[i] for i in v) 
    return memo[x] 

입력 : 이것은 당신이 제시 한 원래의 알고리즘의 반복 버전으로 계산하지만 여기 memoized 반복 버전의 경우

는 잘 모르겠어요 , 따라 달라집니다. 그런 다음 그 숫자를 계산합니다. 맨 아래부터 x 방향으로갑니다.

코드는 calc_dep 테스트 때문에 매우 빠릅니다. 여러 종속성을 계산하지 않습니다. 결과적으로 400 밀리 초 미만의 시간에 게임 (10000)을 할 수 있지만 원래는 걸립니다. 얼마나 걸릴지 모르겠습니다. 오랜 시간.

Elapsed: 1000 0:00:00.029000 
Elapsed: 2000 0:00:00.044000 
Elapsed: 4000 0:00:00.086000 
Elapsed: 8000 0:00:00.197000 
Elapsed: 16000 0:00:00.461000 
Elapsed: 32000 0:00:00.969000 
Elapsed: 64000 0:00:01.774000 
Elapsed: 128000 0:00:03.708000 
Elapsed: 256000 0:00:07.951000 
Elapsed: 512000 0:00:19.148000 
Elapsed: 1024000 0:00:34.960000 
Elapsed: 2048000 0:01:17.960000 
Elapsed: 4096000 0:02:55.013000 

그것은 합리적으로 활발한입니다 : 여기

은 성능 측정입니다.