재귀 함수란? (Recursion)

재귀(Recursion)

재귀란 쉽게 말해 자기 자신을 호출하는 함수 입니다.

문제를 더 작은 하위 문제로 나눈 것을 의미합니다.

재귀의 개념은 수학적 사고에 기반하고, 코드를 작성하기 전에 문제를 해결하는 재호출 로직을 발견해야 합니다.

 

재귀는 해결을 위한 특정 기능을 재호출 한다는 측면이고, 분할정복은 문제를 분할하고 해결하는 구체적인 방법론 입니다.

분할정복법을 활용하기 위해서는 재귀개념이 필요합니다.

 

예를 들어보겠습니다.

sample_list = [1, 2, 3, 4, 5]

def sum_list(x):
	sum = 0
    for i in x:
    	sum = sum + i
    
    return sum
    
sum_list(sample_list)

위의 문제를 하위 문제로 분리하면 이렇게 됩니다.

1 + 2 + 3 + 4 + 5
(1 + (2 + 3 + 4 + 5))
(1 + (2 + (3 + 4 + 5)))
(1 + (2 + (3 + (4 + 5))))
(1 + (2 + (3 + (4 + (5)))))

• 위의 분리된 내용을 의사코드를 활용하여 먼저 로직을 해석해본다.

sum_list(items)
    if the length of items is 1
        return the 1 item in the list

sum_list(items)
    if the length of items is 1
        return the 1 item in the list
    otherwise
        return the first item from the list + sum_list(the rest of the items)

def sum_list(items):
    if len(items) == 1:
        return items[0]
    else:
        return items[0] + sum_list(items[1:])

재귀의 조건 1) base case(기본 케이스 또는 조건)가 있어야 된다.

• 알고리즘은 특성상 반복을 중지할 수 있다.
• 아래의 sum_list 함수를 사용하여 알고리즘이 반복을 중지하도록 하는 조건은 무엇일까?

def sum_list(items):
    if len(items) == 1: # Base Case
        return items[0]
    else:
        return items[0] + sum_list(items[1:])

# test case 
#sum_list(1)
#sum_list([1,3])

재귀의 조건 2) 추가 조건과 기본 케이스의 차이를 확인한다.

• 아래의 재귀에서 sum_list에 전달된 items는 한 항목씩 감소한다.
  • 예를 들어, 첫 번째 재귀에서 항목은 [2,3,4,5]이고 다음 재귀에서는 내부적으로 items [3,4,5]이다.

def sum_list(items):
    if len(items) == 1: # Base Case(항목이 1개인 경우가 기본 케이스)
        return items[0]
    elif len(items) > 1:
        print("items:", items[0:])
        return items[0] + sum_list(items[1:]) # items[:]는 한 항목씩 감소한다.
        
print("sum_list:", sum_list([2, 3, 4, 5]))

재귀의 조건 3) 반드시 자기 자신(함수)를 호출해야 한다.

• 세 번째 규칙은 알고리즘이 자신을 호출해야한다.
  • 함수의 마지막 줄에서 재귀작업을 수행한다.

def add_two(num): # 매개변수
    return num + 2  # 반환값

def add_four(num):  # 매개변수
    return add_two(add_two(num))  # 반환값으로 매개변수가 있는 함수를 넣는다.

print(add_two(2))
print(add_four(6))

재귀 제한

• 파이썬에서는 재귀 깊이의 제한을 1000으로 기본 설정하고 있다.
• 재귀 함수의 호출이 1000에 도달했을 때 RecursionError가 발생한다.

# 파이썬에서 최대 재귀 깊이 확인하기
import sys
print(sys.getrecursionlimit())

def sum_number(n):
    if n <= 0:
        return 0
    else:
        return n + sum_number(n-1)

print(sum_number(3000))
# 파이썬이 정한 최대 재귀 깊이보다 재귀의 깊이가 더 깊어질 경우 에러 발생!

• 위 예제의 에러를 해결하려면 최대 재귀 깊이를 늘려야 한다.
  • setrecursionlimit() 함수를 사용하면 재귀 제한을 설정할 수 있다.

import sys
sys.setrecursionlimit(3500) # 재귀 깊이 3500으로 변경 

def sum_number(n):
    if n <= 0:
        return 0
    else:
        return n + sum_number(n-1)

print(sum_number(3000))