재귀 알고리즘, 재귀 함수 (Recursive) 기초

재귀 함수 Recursive : 정의 단계에서 자신을 재참조하는 함수
재귀 알고리즘 Recursive Algorithms : 하나의 함수에서 자기 자신을 다시 호출하여 작업을 수행하는 알고리즘

 

재귀적이다? 어떤 사건이 자신을 포함하고 다시 자기 자신을 사용하여 정의된다.

 

---

반응형

 

 

 

재귀 함수의 구성 요소 및 원리

* 구성 요소 : 하위 문제, 베이스 케이스, 재귀 케이스

1. 본 문제에서 하위 문제를 찾는다.
   tip! '파라미터로 받은 인풋의 사이즈를 -1 하면 어떻게 될까?' 생각해보기
2. 베이스 케이스와 재귀 케이스를 정한다.
   베이스 케이스 : 하위 문제 없는 빈 리스트나 요소가 1개인 경우
   재귀 케이스 : 하위 문제를 찾아야 하는 요소가 2개 이상
3. 이를 토대로 함수를 구현한다.

 

 

🔍 [예시] 리스트 뒤집기

리스트 [1, 2, 3, 4, 5]가 있을 때, 이를 뒤집는 기능을 하는 재귀 함수를 작성해보자.

 

[1, 2, 3, 4]를 뒤집고, 그 앞에 [5]를 붙이면 해결이 된다. [5]가 베이스 케이스, [4, 3, 2, 1]이 재귀 케이스가 된다.

 

함수로 구현해보면 다음과 같다.

 

def reverse(my_list) : 
	if len(my_list) <= 1 :
    	# base case
        return my_list
    else :
    	# recursive case
        # [5] + [4, 3, 2, 1]
        return my_list[-1:] + reverse(my_list[:-1])

 

만약 리스트의 길이가 1이나 0이라면 뒤집을 필요가 없기 때문에 그대로 my_list를 출력하면 된다. 또는 my_list의 마지막 요소를 먼저 출력하고, 다시 또 reverse 함수를 -1한 값을 불러와서 반복한다.

 

1. 현재 mylist = [1, 2, 3, 4, 5]이다. mylist[-1:]에서 5를 담아두고, reverse(my_list[:-1])에 의해서 reverse([1, 2, 3, 4])를 불러온다.

2. 현재 mylist = [1, 2, 3, 4]이다. mylist[-1:]에서 4를 담아두고, reverse(my_list[:-1])에 의해서 reverse([1, 2, 3])를 불러온다.

3. 현재 mylist = [1, 2, 3]이다. mylist[-1:]에서 3를 담아두고, reverse(my_list[:-1])에 의해서 reverse([1, 2])를 불러온다.

4. 현재 mylist = [1, 2]이다. mylist[-1:]에서 2를 담아두고, reverse(my_list[:-1])에 의해서 reverse([1])를 불러온다.

5. 현재 mylist = [1]이다. len(mylist) == 1 이므로, my_list인 1을 담아둔다.

 

결과적으로 [5, 4, 3, 2, 1]이 출력된다.

 

 

 

 

재귀 함수와 반복문

위 코드에서 살펴봤다시피, 재귀 함수의 내용은 반복문으로도 작성 가능한 내용이다.

 

# 재귀함수
def countdown(n) : 
	if n > 0 :
    	print(n)
        countdown(n-1)

# 반복문
def countdown(n) :
	i = n
    while i > 0 :
    	print(i)
        i -= 1

 

 

⚠️ 더군다나 재귀함수는 스택 오버플로우 에러 (Stack Overflow Error)를 주의해야 한다.

해당 변수의 크기가 Stack보다 크거나, 함수를 무한으로 호출하고 있을 때, 혹은 Stack을 넘어가 다른 곳에 위치하고 있는 경우 Stack overflow가 발생한다.

 

 

🤔 그럼에도 불구하고 왜 반복문이 아니라 재귀 함수를 사용할까?

 

➀ 어떤 문제들은 재귀 함수로 작성하는 게 더 깔끔하고 쉬울 수도 있고, 

➁ 반복문으로 구현하게 되더라도 재귀적인 접근 방식으로 해결책을 찾을 수 있기 때문에 

 

재귀 함수가 어려워도 반복문이 아니라 재귀 함수를 쓰는 경우가 있다.

 

 

---

 

 

🔆 자료구조와 알고리즘 살펴보기

자료구조와 알고리즘