[자료구조] 3. 재귀함수(Recursion) 이해하기 (feat. codestates, self_tutorial)

 

 

 

 

안녕하십니까 다제입니다. 

 

이제부터는 재귀에 대해서 공부를 진행해보고자 합니다.

많이 어렵다고 소문난 개념이지만, 저와 함께 하시면 쉽게 하실 수 있습니다!

 

함께 가보시죠!

 

 

---

 

 

1. 재귀함수 정의 

재귀함수란? 자기 자신을 호출하는 함수를 말합니다. 

 

응? 이게 무슨 말일까요? 

우리는 일반적으로 함수를 만들어줄 때 특정한 변수, 특정한 값을 리턴하도록 만들었습니다. 

그런데, 함수의 맨 마지막에 자신의 함수명을 넣는 것이죠!

 

그렇게되면 자기 자신을 계속~ 계속~ 계속~ 실행하게 됩니다. 

말보단 언제나 코드로 보는게 저희는 편하니 한번 보도록 할까요?

 

두 가지 예시를 가지고 왔습니다. 

하나는 카운트 다운을 하는 함수이고, 하나는 펙토리얼 함수 입니다. 

 

def count_down_func(n):
  if n > 0 :
    print(n)
    count_down_func(n-1)
 
print(count_down_func(5))

위에서 말씀드린 바와 같이 return이 없고 자기 함수 자신의 이름이 기재되어 있는 것을 보실 수 있습니다. 

 

재귀적으로 문제를 푼다는 것은 부분 문제의 답을 이용해서 기존 문제를 푸는 것입니다.

그런데, 모든 경우의 수가 하나의 규칙으로 정의되지 않을 수 있습니다. 

팩토리얼의 경우, n이 0일때 별도의 처리를 해줘야하는데요. 이런 경우를 base case라고 하고, n이 0보다 클 경우, recursive case라고 합니다. 즉, 재귀를 풀때는 base case랑 recursive case를 항상 생각해야합니다. 

# 최초 생각한 코드 
def factorial(n):
  if n == 0 :
    return 1
  elif n == 1:
    return 1
  elif n > 1:
    return n * factorial(n-1)

# 한결 간결하게 기재한 코드 
# 이렇게 return을 두번 쓸 수 동 있습니다! 
def factorial_func(n):
    if n == 0:
    	return 1
    return n * factorial_func(n-1)

print(factorial_func(5))

또 하나의 예제는 재귀를 할때 가장 많이 사용되는 예시인 펙토리얼 함수를 만들어보았습니다. 

간단히 설명을 드리면 처음에 n=5입니다. 

그럼 if절을 생략하고 return으로 넘어가게 됩니다. 

-> 5  * factorial_func(4)

-> 5  * 4 * factorial_func(3)

-> 5  * 4 * 3 * factorial_func(2)

-> 5  * 4 * 3 * 2 * factorial_func(1)

그러다가 factorial_func(1)은 1을 리턴해주기 때문에 1을 곱해주면 120이 출력이 됩니다. 

 

 

# 반복문으로 풀기

my_list = [1,2,3,4,5]
def sum_list(items):
    sum = 0
    for i in items:
        sum = sum + i
    return sum

sum_list(my_list)

#--------------------------------------------

# 재귀적으로 풀기 

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

위에 펙토리얼과 정말 똑같습니다. 단지 들어오는 값이 리스트로 변경되었다는 것뿐입니다.

리스트의 len를 줄여주는 역할을 sum_list(items[1:])이 하게 됩니다.

천천히 여유를 가지고 생각하시면 이해가 되실 겁니다.

 

 

---

 

 

2. 주의사항 

 -. 반복문으로 풀 수 있는 문제는 재귀로도 풀 수 있고

 -. 재귀로 풀 수 있는 문제는 반복문으로도 풀 수 있습니다. 

 -. 재귀는 코드를 깔끔하게 기재하기 위해 사용하는데요

 -. 단, 재귀함수에서는 돌아갈 위치를 우리가 정해주지 않기 때문에 컴퓨터 내부에서 돌아갈 위치를 저장해놓습니다. 

 -. 돌아갈 위치를 저장하는 것을 call stack이라고 합니다.

 -. 그런데, 재귀함수 호출이 너무 많은 call stack이 계속 증가하겠죠? 그럼 기록할 공간이 없어지게 되고 과부하로 인해 프로그램이 중단이 됩니다. 이때 발생되는 오류가 StackoverflowError가 발생되게 됩니다. 

 -. 저희가 자주 사용하는 stackoverflow 웹사이트가 해당 오류에서 이름을 따왔다고 합니다. 신기하더라구요!

 -. 파이썬의 경우, call stack을 1000개 정도만 허용하니 이점 참고하시어 코드를 구상하셔야 합니다. 

 

 

---

 

 

3. 재귀함수 예제

 -. 피보나치 수열

 -. 자릿수 합 구하기

 -. 리스트 뒤집기

 -. 이진 탐색 재귀로 구현하기

 -. 하노이의 탑 

 

 

---

 

 

위와 같이 재귀함수 예제는 다양하게 있습니다. 

 

백준, 프로그래머스 등 코딩테스트 사이트에 방문하시어 위와 유사한 문제들을 풀어보시어 재귀함수에 보다 익숙해지시는걸 추천드립니다. 

 

우리 열심히 해서 꼭 원하는 기업에 취직하시게요!!

 

오늘도 방문해주셔서 감사드립니다. 

 

해당 글이 도움이 되셨다면 공감(아래 하트버튼) 클릭 부탁드립니다.