재귀 recursion, 파이썬

Recursion _The repeated application of the same procedure to a smaller problem

예시 : 마트료시카

 

Recursion lets us tackle complex problems by reducing the problem to a simpler one.

긴 줄의 한가운데 있는 사람이 자신이 몇 번째인지 알기 위해서 바로 앞사람에게 순서를 물어보고, 질문이 맨 앞사람에게까지 이어져 맨 앞 사람 앞에 사람이 없는 것을 알고 첫번째라는것을 뒷사람에게 알려줘 또 순서대로 자기 순서를 알게 되는 것과 유사함 

 

In programming, recursion is a way of doring a repetitive task by having a function call itself.

재귀 함수는 일반적으로 특정 조건에 도달할 때까지 수정된 매개변수를 사용하여 자신을 호출하는데, 이를 base case라고 한다.

 

앞의 예시에서 base case는 가작 작은 마트료시카와 줄의 맨 앞에 서있는 사람이다.

def factorial(n):  # function def
	if n < 2:  # base case
    	return 1
    return n * factorial(n-1)  #recursive case, creates loop

# Quiz solution
def sum_positive_numbers(n):
    # The base case is n being smaller than 1
    if n < 1:
        return n
    # The recursive case is adding this number to
    # the sum of the numbers smaller than this one.
    return n + sum_positive_numbers(n-1)

print(sum_positive_numbers(3)) # Should be 6
print(sum_positive_numbers(5)) # Should be 15

 

for이나 while 루프를 사용하면 되는데 왜 재귀함수가 필요한가?

특정 문제에 대한 솔루션은 재귀함수를 사용하면 작성과 이해가 더 쉽다(팩토리얼이나 시그마 등).

 

it 중심적 재귀 구조의 예시

1. 중첩된 디렉토리의 수의 계산

base case는 하위 디렉토리가 없는 디렉토리

이 경우 함수는 파일의 수량만 반환

풀더안의 폴더안의 폴더같은 재귀구조에서는 재귀 함수를 사용하는 것이 더 쉽다.

 

2. 다른 그룹을 포함할 수 있는 사용자 그룹을 처리하는 모든 것

Active Directory 나 LDAP 같은 관리 도구를 사용할 때가 이에 해당한다.

 

한계

파이썬은 제한에 도달할 때까지 재귀 함수를 1000회 호출 가능

RecursionError: maximum recursion depth exceeded in comparison 

-> 재귀 호출의 최대 제한에 도달했음을 알려준다.

 

따라서 다양한 시나리오에서 재귀를 사용할 수 있지만 1천 개 정도의 중첩 수준이 아닌 재귀 구조에서만 재귀를 사용하는 것이 좋다. 

 

재귀 함수의 일반적인 구조

def recursive_function(parameters):
	if base_case_condition(parameters):
    		return base_case_value
    	recursive_function(modified_parameters)

참고

Wikipedia 재귀 페이지

Google에서 재귀를 검색

 

출처 - coursera x kmooc 파이썬 단기집중과정 3주차