Python Language
재귀

비고

1에서 n까지의 합계

n 이 자연수 인 1 에서 n 까지의 숫자의 합을 찾으려면 1 + 2 + 3 + 4 + ... + (several hours later) + n 있습니다. 또는 for 루프를 작성할 수도 있습니다.

n = 0
for i in range (1, n+1):
    n += i

또는 재귀라고하는 기술을 사용할 수 있습니다.

def recursion(n):
    if n == 1:
        return 1
    return n + recursion(n - 1)

재귀는 위의 두 가지 방법에 비해 장점이 있습니다. 재귀는 1 + 2 + 3 의 합계에 대해 1 + 2 + 3 을 쓰는 것보다 시간이 덜 걸립니다. recursion(4) 경우 재귀를 사용하여 뒤로 작업 할 수 있습니다.

함수 호출 : (4 -> 4 + 3 -> 4 + 3 + 2 -> 4 + 3 + 2 + 1 -> 10)

for 루프는 엄격하게 전달하는 반면 (1 -> 1 + 2 -> 1 + 2 + 3 -> 1 + 2 + 3 + 4 -> 10). 때때로 재귀 적 솔루션은 반복적 솔루션보다 간단합니다. 이것은 연결된 목록의 역전을 구현할 때 분명합니다.

재귀의 목적, 방법 및시기

재귀는 원래 함수 호출이 종료되기 전에 함수 호출이 동일한 함수를 다시 호출하게 할 때 발생합니다. 예를 들어 잘 알려진 수식 x! (즉, 계승 연산). 팩토리얼 연산은 다음과 같이 모든 음이 아닌 정수에 대해 정의됩니다.

• 숫자가 0이면 대답은 1입니다.
• 그렇지 않은 경우, 해당 숫자는 해당 숫자보다 1의 계승을 곱한 것입니다.

파이썬에서 계승 연산의 순진한 구현은 다음과 같은 함수로 정의 할 수 있습니다.

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n - 1)

재귀 함수는 때때로 이해하기 어려울 수 있으므로이 단계별 설명을 살펴 보겠습니다. 식 factorial(3) 고려하자. 이 함수 호출과 모든 함수 호출은 새로운 환경을 만듭니다. 환경은 기본적으로 식별자 (예 : n , factorial , print 등)를 해당 값으로 매핑하는 테이블입니다. 언제든지 locals() 사용하여 현재 환경에 액세스 할 수 있습니다. 첫 번째 함수 호출에서 정의 된 유일한 로컬 변수는 n = 3 입니다. 따라서 locals() 인쇄 locals() 는 {'n': 3} 됩니다. n == 3 이므로 반환 값은 n * factorial(n - 1) 됩니다.

이 다음 단계에서는 상황이 다소 혼란 스러울 수 있습니다. 우리의 새로운 표현을 보면, 우리는 이미 n 이 무엇인지를 알고 있습니다. 그러나, 우리는 어떤 factorial(n - 1) 인지 아직 모른다. 첫째, n - 1 은 2 평가됩니다. 그러면 2 가 factorial 값으로 n 값으로 전달됩니다. 이것은 새로운 함수 호출이기 때문에이 새로운 n 을 저장하기위한 두 번째 환경이 생성됩니다. A 가 첫 번째 환경이고 B 가 두 번째 환경이되도록하십시오. A는 여전히 존재하고 {'n': 3} 과 동일하지만 B ( {'n': 2} 와 같습니다))가 현재 환경입니다. 함수 본문을 보면 반환 값은 다시 n * factorial(n - 1) 입니다. 이 표현식을 평가하지 않고 원래의 return 표현식으로 대체 해 봅시다. 이렇게함으로써, 우리는 정신적으로 B를 폐기하고, 그래서 대체하는 것을 잊지 n 따라 (B에 즉, 참조의 n 대체됩니다 n - 1 의 사용 ' n ). 이제 원래의 리턴 표현식은 n * ((n - 1) * factorial((n - 1) - 1)) 됩니다. 잠시 시간을내어 이것이 왜 그렇게되는지 이해하도록하십시오.

자, 그 factorial((n - 1) - 1)) 부분을 ​​평가합시다. A 의 n == 3 이므로 1 을 factorial 전달합니다. 그러므로 우리는 {'n': 1} 과 같은 새로운 환경 C 를 만들고 있습니다. 다시, 반환 값은 n * factorial(n - 1) 입니다. 그래서 원래의 리턴 표현식을 이전에 조정했던 것과 비슷하게 "원래"리턴 표현식의 factorial((n - 1) - 1)) 을 대체합시다. "원래"표현식은 이제 n * ((n - 1) * ((n - 2) * factorial((n - 2) - 1))) 입니다.

거의 끝났어. 이제 factorial((n - 2) - 1) 을 평가할 필요가 있습니다. 이번에는 0 전달합니다. 따라서이 값은 1 평가됩니다. 자, 마지막으로 치환을 해봅시다. "원래"리턴 표현식은 이제 n * ((n - 1) * ((n - 2) * 1)) 입니다. 원래 리턴 표현식이 A 에서 평가된다는 점을 상기하면 표현식은 3 * ((3 - 1) * ((3 - 2) * 1)) . 이것은 물론 6으로 평가됩니다. 이것이 정답이라고 확인하려면 3! == 3 * 2 * 1 == 6 상기하십시오 3! == 3 * 2 * 1 == 6 . 더 이상 읽지 않기 전에, 환경의 개념과 재귀에 적용하는 방법을 완전히 이해했는지 확인하십시오.

if n == 0: return 1 기본 case라고합니다. 이것은 재귀를 나타내지 않기 때문입니다. 기본 케이스는 절대적으로 필요합니다. 하나도 없으면 무한 재귀가됩니다. 그렇게 말하면 적어도 하나의 기본 케이스가있는 한 원하는만큼의 케이스를 가질 수 있습니다. 예를 들어, 다음과 같이 동등하게 factorial 을 작성할 수 있습니다.

def factorial(n):
    if n == 0:
        return 1
    elif n == 1:
        return 1
    else:
        return n * factorial(n - 1)

재발 사례가 여러 개있을 수도 있지만 비교적 드문 일이기 때문에 정신적으로 처리하기가 어려울 수 있습니다.

"병렬"재귀 함수 호출을 사용할 수도 있습니다. 예를 들어 다음과 같이 정의 된 피보나치 시퀀스 를 생각해보십시오.

• 숫자가 0이면 대답은 0입니다.
• 숫자가 1이면 대답은 1입니다.
• 그렇지 않은 경우, 대답은 이전 두 피보나치 수의 합계입니다.

우리는 다음과 같이 정의 할 수 있습니다.

def fib(n):
    if n == 0 or n == 1:
        return n
    else:
        return fib(n - 2) + fib(n - 1)

나는 factorial(3) 에서했던 것처럼이 함수를 철저히 지키지 않을 것이지만, fib(5) 의 최종 반환 값은 다음과 같은 ( 구문 적으로 유효하지 않은) 표현식과 같습니다.

(
  fib((n - 2) - 2)
  +
  (
    fib(((n - 2) - 1) - 2)
    +
    fib(((n - 2) - 1) - 1)
  )
)
+
(
  (
    fib(((n - 1) - 2) - 2)
    +
    fib(((n - 1) - 2) - 1)
  )
  +
  (
    fib(((n - 1) - 1) - 2)
    +
    (
      fib((((n - 1) - 1) - 1) - 2)
      +
      fib((((n - 1) - 1) - 1) - 1)
    )
  )
)

이것은 물론 5 평가되는 (1 + (0 + 1)) + ((0 + 1) + (1 + (0 + 1))) 됩니다.

이제 어휘 용어에 대해 더 자세히 살펴 보겠습니다.

• 꼬리 호출 은 값을 반환하기 전에 수행 할 마지막 작업 인 재귀 함수 호출입니다. 명확히하기 위해, return foo(n - 1) 은 꼬리 호출이지만 return foo(n - 1) + 1 은 return foo(n - 1) + 1 하지 않는다.
• 테일 호출 최적화 ( Tail call optimization : Tail call optimization )는 재귀 함수에서 재귀를 자동으로 줄이는 방법입니다.
• 꼬리 전화 제거 ( Tail call elimination , TCE)는 꼬리 호출을 재귀없이 평가할 수있는 식으로 축소하는 것입니다. TCE는 일종의 TCO입니다.

테일 호출 최적화는 여러 가지 이유로 유용합니다.

• 인터프리터는 환경에 의해 점유 된 메모리 양을 최소화 할 수 있습니다. 컴퓨터에 무제한 메모리가 없으므로 과도한 재귀 함수 호출로 인해 스택 오버플로가 발생 합니다.
• 인터프리터는 스택 프레임 스위치 수를 줄일 수 있습니다.

파이썬에는 여러 가지 이유로 TCO가 구현되어 있지 않습니다. 따라서 이러한 한계를 극복하기 위해서는 다른 기술이 필요합니다. 선택 방법은 유스 케이스에 달려있다. 직관적으로 factorial 과 fib 의 정의는 다음과 같이 비교적 쉽게 반복 코드로 변환 될 수 있습니다.

def factorial(n):
    product = 1
    while n > 1:
        product *= n
        n -= 1
    return product

def fib(n):
    a, b = 0, 1
    while n > 0:
        a, b = b, a + b
        n -= 1
    return a

일반적으로 재귀를 수동으로 제거하는 가장 효율적인 방법이지만보다 복잡한 기능의 경우 다소 어려워 질 수 있습니다.

또 다른 유용한 도구는 파이썬의 lru_cache 데코레이터로 여분의 계산 횟수를 줄이는 데 사용할 수 있습니다.

파이썬에서 재귀를 피하는 방법에 대한 아이디어가 있지만 재귀를 언제 사용해야 합니까? 대답은 "자주"아닙니다. 모든 재귀 함수는 반복적으로 구현 될 수 있습니다. 어떻게 그렇게하는지 파악하는 것입니다. 그러나 재귀가 괜찮은 경우는 거의 없습니다. 재귀는 예상되는 입력이 많은 수의 재귀 함수 호출을 발생시키지 않을 때 Python에서 일반적입니다.

재귀가 관심있는 주제라면, Scheme이나 Haskell과 같은 기능적 언어를 공부하길 바랍니다. 이러한 언어에서는 재귀가 훨씬 유용합니다.

위의 피보나치 시퀀스 예제는 Python에서 정의를 적용하고 나중에 lru 캐시를 사용하는 방법을 잘 보여 주지만 각 비 기본 경우에 대해 2 회 재귀 호출을 수행하므로 비효율적 인 실행 시간을 갖습니다. 함수에 대한 호출 수가 n 기하 급수적으로 증가합니다.
오히려 비 직관적으로보다 효율적인 구현은 선형 재귀를 사용합니다.

def fib(n):
    if n <= 1:
        return (n,0)
    else:
        (a, b) = fib(n - 1)
        return (a + b, a)

하지만 한 쌍 의 숫자를 반환하는 문제가 있습니다. 이는 일부 함수가 실제로 재귀에서 많이 얻지 못함을 강조합니다.

재귀를 사용한 트리 탐색

다음 트리가 있다고 가정 해보십시오.

root
- A
  - AA
  - AB
- B
  - BA
  - BB
    - BBA

이제 모든 요소의 이름을 나열하려면 간단한 for 루프를 사용하면됩니다. get_name() 함수는 노드 이름 문자열을 반환하고, get_children() 함수는 트리의 주어진 노드의 모든 하위 노드 목록을 반환하고, get_root() 함수는 루트 노드를 얻는다.

root = get_root(tree)
for node in get_children(root):
    print(get_name(node))
    for child in get_children(node):
        print(get_name(child))
        for grand_child in get_children(child):
            print(get_name(grand_child))
# prints: A, AA, AB, B, BA, BB, BBA

이것은 잘 작동하지만 빠르지 만 하위 노드에 하위 노드가있는 경우에는 어떻게해야합니까? 그리고 그 하위 노드는 더 많은 하위 노드를 가질 수 있습니다 ... 얼마나 많은 것들이 있을지 미리 모르는 경우에는 어떻게합니까? 이 문제를 해결하는 방법은 재귀를 사용하는 것입니다.

def list_tree_names(node):
    for child in get_children(node):
        print(get_name(child))
        list_tree_names(node=child)

list_tree_names(node=get_root(tree))
# prints: A, AA, AB, B, BA, BB, BBA

인쇄하지 않고 모든 노드 이름의 일 치 목록을 리턴하려고합니다. 이는 롤링 목록을 매개 변수로 전달하여 수행 할 수 있습니다.

def list_tree_names(node, lst=[]):
    for child in get_children(node):
        lst.append(get_name(child))
        list_tree_names(node=child, lst=lst)
    return lst

list_tree_names(node=get_root(tree))
# returns ['A', 'AA', 'AB', 'B', 'BA', 'BB', 'BBA']

최대 재귀 깊이 늘리기

가능한 재귀의 깊이에는 제한이 있습니다. 재귀의 깊이는 Python 구현에 따라 다릅니다. 한계에 도달하면 RuntimeError 예외가 발생합니다.

RuntimeError: Maximum Recursion Depth Exceeded

다음은이 오류를 일으킬 수있는 프로그램의 예입니다.

def cursing(depth):
  try:
    cursing(depth + 1) # actually, re-cursing
  except RuntimeError as RE:
    print('I recursed {} times!'.format(depth))
cursing(0)
# Out: I recursed 1083 times!

재귀 깊이 제한은 다음을 사용하여 변경할 수 있습니다.

sys.setrecursionlimit(limit) 

다음을 실행하여 한계의 현재 매개 변수가 무엇인지 확인할 수 있습니다.

sys.getrecursionlimit()

새로운 제한으로 우리는 위의 동일한 방법을 실행합니다.

sys.setrecursionlimit(2000)
cursing(0)
# Out: I recursed 1997 times!

Python 3.5에서 예외는 RunursError에서 파생 된 RecursionError입니다.

꼬리 재귀 - 나쁜 습관

함수에서 반환되는 유일한 것이 재귀 호출이면 꼬리 재귀라고합니다.

다음은 꼬리 재귀를 사용하여 작성된 카운트 다운 예제입니다.

def countdown(n):
    if n == 0:
        print "Blastoff!"
    else:
        print n
        countdown(n-1)

반복을 사용하여 수행 할 수있는 계산은 재귀를 사용하여 수행 할 수도 있습니다. 다음은 꼬리 재귀를 사용하여 작성된 find_max의 버전입니다.

def find_max(seq, max_so_far):
    if not seq:
        return max_so_far
    if max_so_far < seq[0]:
        return find_max(seq[1:], seq[0])
    else:
        return find_max(seq[1:], max_so_far)

꼬리 재귀 호출은 파이썬 컴파일러가 꼬리 재귀 호출 최적화를 처리하지 않기 때문에 파이썬에서 나쁜 습관으로 간주됩니다. 이와 같은 경우 재귀 적 솔루션은 동등한 반복 솔루션보다 많은 시스템 리소스를 사용합니다.

Stack Introspection을 통한 테일 재귀 최적화

기본적으로 Python의 재귀 스택은 1000 프레임을 초과 할 수 없습니다. 이것은 더 빠르지 만 sys.setrecursionlimit(15000) 을 설정함으로써 변경 될 수 있지만,이 방법은 더 많은 메모리를 소비합니다. 대신, 스택 인트로 스펙 션을 사용하여 Tail Recursion 문제를 해결할 수도 있습니다.

#!/usr/bin/env python2.4
# This program shows off a python decorator which implements tail call optimization. It
# does this by throwing an exception if it is it's own grandparent, and catching such 
# exceptions to recall the stack.

import sys

class TailRecurseException:
    def __init__(self, args, kwargs):
        self.args = args
        self.kwargs = kwargs

def tail_call_optimized(g):
"""
This function decorates a function with tail call
optimization. It does this by throwing an exception
if it is it's own grandparent, and catching such
exceptions to fake the tail call optimization.
  
This function fails if the decorated
function recurses in a non-tail context.
"""
      
    def func(*args, **kwargs):
        f = sys._getframe()
        if f.f_back and f.f_back.f_back and f.f_back.f_back.f_code == f.f_code:
            raise TailRecurseException(args, kwargs)
        else:
            while 1:
                try:
                    return g(*args, **kwargs)
                except TailRecurseException, e:
                    args = e.args
                    kwargs = e.kwargs
    func.__doc__ = g.__doc__
    return func

재귀 함수를 최적화하기 위해 @tail_call_optimized 데코레이터를 사용하여 함수를 호출 할 수 있습니다. 위에서 설명한 데코레이터를 사용하는 일반적인 재귀 예제 중 일부는 다음과 같습니다.

요인 예 :

@tail_call_optimized
def factorial(n, acc=1):
  "calculate a factorial"
  if n == 0:
    return acc
  return factorial(n-1, n*acc)

print factorial(10000)
# prints a big, big number,
# but doesn't hit the recursion limit.

피보나치 예 :

@tail_call_optimized
def fib(i, current = 0, next = 1):
  if i == 0:
    return current
  else:
    return fib(i - 1, next, current + next)

print fib(10000)
# also prints a big number,
# but doesn't hit the recursion limit.