재귀함수(Recursive Function)
자기 자신을 호출하는 함수
예시를 들기전 '팩토리얼'이란
n! : 자연수 1부터 자연수 n까지의 곱
ex) 4! = 1 x 2 x 3 x 4 = 24
* 예외! : 0! = 1, 1! = 1
Base case 와 Recursive case
재귀적으로 문제를 정리할 때는 base case 와 Recursive case를 생각해야 한다.
Base case
0!와 같이 재귀적으로 문제를 해결할 필요 없이 바로 답을 알 수 있는 경우(= 따로 풀어야할 부분문제가 없음)
* 재귀적으로 문제를 해결한다 = 같은 형태의 더 작은 문제(부분 문제 = Subproblem)를 푼다
Recursive case
재귀적으로 부분문제를 푸는 경우
5!을 풀기위해서는 그의 부분 문제인 4!를 풀면 되고
4!를 풀기위해서는 → 3!를
3!를 풀기위해서는 → 2!를
즉, n이 0보다 큰 경우 = n! = (n-1)! x n 이라고 볼 수 있음
- Base case 와 Recursive case를 나누어 함수 작성
def factorial(n):
if n == 0:
return 1
return factorial(n - 1) * n
print(factorial(4))재귀함수의 주의할 점
Call Stack: 컴퓨터 프로그램에서 현재 실행 중인 서브루틴에 관한 정보를 저장하는 스택 자료구조
즉, 함수가 끝나면 다시 돌아올 위치를 기록해 두는 곳
함수를 재귀적으로 너무 많이 호출하게 되면 콜스택이 계속해서 쌓이면서 더이상 기록할 공간이 없어지게 됨 => 프로그램 중단
Stack Overflow Error: 콜스택이 너무 많이 쌓여 한계점에 도달했을 때 뜨는 에러
파이썬에서는 콜스택을 1,000개만 허가해줌
-> 즉, factorial(2000)과 같이 너무 큰 파라미터를 넘겨주면 RecursionError와 함께 프로그램이 중단 됨
재귀함수 관련 문제
- 문제를 푸는 방법
우선, Base case 와 Recursive case가 무엇일지 생각한다
1. 피보나치 수열
피보나치 수열: 첫 번째 항과 두 번째 항이 11이고, 세 번째 항부터는 바로 앞의 두 항의 합으로 정의된 수열
이러한 방식으로 피보나치 수열의 첫 10개 항은 1, 1, 2, 3, 5, 8, 13, 21, 34, 55가 됨
# n번째 피보나치 수를 리턴
def fib(n):
if n < 3:
return 1
return fib(n - 1) + fib(n - 2)
# 코드를 입력하세요.
# 테스트: fib(1)부터 fib(10)까지 출력
for i in range(1, 11):
print(fib(i))< 결과 >
1
1
2
3
5
8
13
21
34
55
2. 숫자 합(삼각 수)
n번째 삼각수(triangle number)는 자연수 1부터 n까지의 합입니다. 파라미터로 정수값 n을 받고 n번째 삼각수를 리턴해주는 재귀 함수 triangle_number를 쓰세요. n은 1 이상의 자연수라고 가정합시다.
# 1부터 n까지의 합을 리턴
def triangle_number(n):
if n == 1:
return 1
return triangle_number(n - 1) + n
# 코드를 입력하세요
# 테스트: triangle_number(1)부터 triangle_number(10)까지 출력
for i in range(1, 11):
print(triangle_number(i))< 결과 >
1
3
6
10
15
21
28
36
45
55
3. 자릿수 합
파라미터로 정수값 n을 받고 n의 각 자릿수의 합을 리턴해주는 재귀함수 sum_digits를 쓰세요.
# n의 각 자릿수의 합을 리턴
def sum_digits(n):
if n < 10:
return n
return n % 10 + sum_digits(n // 10)
# 코드를 작성하세요.
# 테스트
print(sum_digits(22541))
print(sum_digits(92130))
print(sum_digits(12634))
print(sum_digits(704))
print(sum_digits(3755))< 결과 >
14
15
16
11
20
4. 리스트 뒤집기
파라미터로 리스트 some_list를 받고, 뒤집힌 리스트를 리턴해 주는 재귀 함수 flip을 쓰세요.
# 파라미터 some_list를 거꾸로 뒤집는 함수
def flip(some_list):
if len(some_list) == 0 or len(some_list) == 1:
return some_list
return flip(some_list[-1:]) + flip(some_list[:-1])
# 코드를 입력하세요.
# 테스트
some_list = [1, 2, 3, 4, 5, 6, 7, 8, 9]
some_list = flip(some_list)
print(some_list)< 결과 >
[9, 8, 7, 6, 5, 4, 3, 2, 1]
5. 재귀로 구현한 이진탐색
def binary_search(element, some_list, start_index=0, end_index=None):
# end_index가 따로 주어지지 않은 경우에는 리스트의 마지막 인덱스
if end_index == None:
end_index = len(some_list) - 1
# 찾는 값이 없는 경우
if start_index > end_index:
return None
# mid 값 정의
mid = (start_index + end_index) // 2
# mid 값이 element 와 같을때 mid 값 반환
if some_list[mid] == element:
return mid
if element < some_list[mid]:
return binary_search(element, some_list, start_index, mid - 1)
else:
return binary_search(element, some_list, mid + 1, end_index)
# 코드를 작성하세요.
print(binary_search(2, [2, 3, 5, 7, 11]))
print(binary_search(0, [2, 3, 5, 7, 11]))
print(binary_search(5, [2, 3, 5, 7, 11]))
print(binary_search(3, [2, 3, 5, 7, 11]))
print(binary_search(11, [2, 3, 5, 7, 11]))< 결과 >
0
None
2
1
4
(와 이거 다 구현해 놓고 위에 mid = (start_index + end_index) // 2에서 괄호를 쓰지 않고 더해줘서 계속 마지막 테스트코드만 답이 안나왔다 ㅠㅠㅠㅠ
난 내 코드가 모두 잘못 짜여진 줄 알고 몇 시간을 다시하고 다시하고 했는데.. 후.. 저녀석이었다니... 너무 진빠짐...ㅠㅠ우짜요 과거의 나를 탓해야지 떼잉!)
6. 하노이의 탑 -- 푸는 중..
*참고: 코드잇 강의, 위키백과
