재귀(Recursion)

재귀는 사소하게 해결할 수 있을 정도로

작은 문제에 도달 할 때까지 문제를 더 작은 단위로 나누고 해결함.

재귀는 자기 자신을 호출하는 함수

 

리스트의 숫자를 모두 더하는 것을 예시로 들면 반복함수를 써서 구할 수 있다.

def iterative_sum(numbers):
    total = 0
    for n in numbers:
        total = total + n
    return total

iterative_sum([1, 3, 5, 7, 9])  # => 25

 

만약, for나 while과 같은 loop가 없이 계산하려면 어떻게 하면 될까

 

수학자라면 덧셈이 두 쌍의 매개 변수 인 한 쌍의 숫자에 대해 정의 된 함수라는 것을 상기하여 구할 수 있다.

 

리스트를 추가 할 때부터 숫자를 추가 할 때까지

리스트를 완전히 괄호로 묶은 표현식으로 다시 작성할 수 있습니다.

이러한 표현은 다음과 같다.

 

$ total = (1+(3+(5+(7+9)))) $

$ total = (1+(3+(5+16))) $

$ total = (1+(3+21)) $

$ total = (1+24) $

$ total = 25 $

 

이러한 아이디어를 파이썬 프로그램으로 바꾸려면?

 

먼저,

리스트 번호의 합은

리스트의 첫 번째 요소의 합 (numbers [0])과

나머지리스트에있는 숫자의 합 (numbers [1 :])이라고 말할 수 있습니다.

 

$ sum\,of\,numbers = numbers[0] + numbers[1:] $

 

함수로 표현하면...

 

$ sum_{of}f(numbers)=first(numbers) + sum_{of}f(rest(numbers)) $

 

이 방정식에서 $first (numbers)$는 목록의 첫 번째 요소를 반환하고

$rest (numbers)$는 첫 번째 요소를 제외한 모든 목록을 반환합니다.

 

def sum_of(numbers):
    if len(numbers) == 0:
        return 0

    return numbers[0] + sum_of(numbers[1:])

sum_of([1, 3, 5, 7, 9])  # => 25

먼저, 2행에서 목록이 비어 있는지 확인합니다.

함수에서 escape clause다. 길이가 0 인 목록의 합은 간단함.

0을 리턴하면됨

 

둘째, 5 행에서 함수가 자체를 호출

재귀 함수는 자신을 호출하는 함수입니다.

 

 

 

재귀의 3가지 조건은 다음과 같다.

1. A recursive algorithm must have a base case.
2. A recursive algorithm must change its state and move toward the base case.
3. A recursive algorithm must call itself, recursively.