재귀 용법 (Recursive Call)
이해하기 쉽고, 장황하지 않은 자료를 기반으로 강의를 진행합니다.
6. 재귀 용법 (recursive call, 재귀 호출)¶
고급 정렬 알고리즘엥서 재귀 용법을 사용하므로, 고급 정렬 알고리즘을 익히기 전에 재귀 용법을 먼저 익히기로 합니다.
1. 재귀 용법 (recursive call, 재귀 호출)¶
- 함수 안에서 동일한 함수를 호출하는 형태
- 여러 알고리즘 작성시 사용되므로, 익숙해져야 함
2. 재귀 용법 이해¶
- 예제를 풀어보며, 재귀 용법을 이해해보기
예제¶
- 팩토리얼을 구하는 알고리즘을 Recursive Call 을 활용해서 알고리즘 작성하기
예제 - 분석하기¶
- 간단한 경우부터 생각해보기
- 2! = 1 X 2
- 3! = 1 X 2 X 3
- 4! = 1 X 2 X 3 X 4
- 규칙이 보임: n! = n X (n - 1)!
- 함수를 하나 만든다.
- 함수(n) 은 n > 1 이면 return n X 함수(n - 1)
- 함수(n) 은 n = 1 이면 return n
- 검증 (코드로 검증하지 않고, 직접 간단한 경우부터 대입해서 검증해야 함)
- 먼저 2! 부터
- 함수(2) 이면, 2 > 1 이므로 2 X 함수(1)
- 함수(1) 은 1 이므로, return 2 X 1 = 2 맞다!
- 먼저 3! 부터
- 함수(3) 이면, 3 > 1 이므로 3 X 함수(2)
- 함수(2) 는 결국 1번에 의해 2! 이므로, return 2 X 1 = 2
- 3 X 함수(2) = 3 X 2 = 3 X 2 X 1 = 6 맞다!
- 먼저 4! 부터
- 함수(4) 이면, 4 > 1 이므로 4 X 함수(3)
- 함수(3) 은 결국 2번에 의해 3 X 2 X 1 = 6
- 4 X 함수(3) = 4 X 6 = 24 맞다!
예제 - 코드 레벨로 적어보기¶
In [1]:
def factorial(num):
if num > 1:
return num * factorial(num - 1)
else:
return num
In [2]:
# 코드로 검증
for num in range(10):
print (factorial(num))
예제 - 시간 복잡도와 공간 복잡도¶
factorial(n) 은 n - 1 번의 factorial() 함수를 호출해서, 곱셈을 함
- 일종의 n-1번 반복문을 호출한 것과 동일
- factorial() 함수를 호출할 때마다, 지역변수 n 이 생성됨
시간 복잡도/공간 복잡도는 O(n-1) 이므로 결국, 둘 다 O(n)
3. 재귀 호출의 일반적인 형태¶
In [ ]:
# 일반적인 형태1
def function(입력):
if 입력 > 일정값: # 입력이 일정 값 이상이면
return function(입력 - 1) # 입력보다 작은 값
else:
return 일정값 # 재귀 호출 종료
In [ ]:
# 일반적인 형태2
def function(입력):
if 입력 <= 일정값: # 입력이 일정 값보다 작으면
return 결과값 # 재귀 호출 종료
function(입력보다 작은 값)
return 결과값
In [71]:
# 일반적인 형태2 로 작성한 팩토리얼
def factorial(num):
if num <= 1:
return num
return_value = num * factorial(num - 1) # return num * factorial(num - 1) 로 작성하는 것도 좋음
return return_value
In [72]:
# 코드로 검증
for num in range(10):
print (factorial(num))
재귀 호출은 스택의 전형적인 예¶
- 함수는 내부적오르 스택처럼 관리된다.
- 재귀 호출이 이해가 가지 않는다면? - 코드분석
참고: 파이썬에서 재귀 함수는 깊이가(한번에 호출되는...) 1000회 이하가 되어야 함
4. 재귀 용법을 활용한 프로그래밍 연습¶
프로그래밍 연습
다음 함수를 재귀 함수를 활용해서 완성해서 1부터 num까지의 곱이 출력되게 만드세요
다음 함수를 재귀 함수를 활용해서 완성해서 1부터 num까지의 곱이 출력되게 만드세요
def muliple(data):
if data <= 1:
return data
return -------------------------
multiple(10)
In [82]:
def multiple(data):
return_value = 1
for index in range(1, data+1):
return_value = return_value * index
return return_value
In [7]:
def multiple(data):
if data <= 1:
return data
return data * multiple(data - 1)
for num in range(10):
print (multiple(num))
프로그래밍 연습
숫자가 들어 있는 리스트가 주어졌을 때, 리스트의 합을 리턴하는 함수를 만드세요
숫자가 들어 있는 리스트가 주어졌을 때, 리스트의 합을 리턴하는 함수를 만드세요
참고: 임의 값으로 리스트 만들기 random.sample(0 ~ 99까지 중에서, 임의로 10개를 만들어서 10개 값을 가지는 리스트 변수 만들기 import random data = random.sample(range(100), 10)
In [83]:
import random
data = random.sample(range(100), 10)
data
Out[83]:
프로그래밍 연습
숫자가 들어 있는 리스트가 주어졌을 때, 리스트의 합을 리턴하는 함수를 만드세요 (재귀함수를 써보세요)
숫자가 들어 있는 리스트가 주어졌을 때, 리스트의 합을 리턴하는 함수를 만드세요 (재귀함수를 써보세요)
def sum_list(data):
if len(data) == 1:
return data[0]
return --------------------------------
import random
data = random.sample(range(100), 10)
print (sum_list(data))
In [89]:
def sum_list(data):
return_value = 0
for item in data:
return_value = return_value + item
return return_value
data_list = random.sample(range(100), 10)
sum_list(data_list)
Out[89]:
In [92]:
data_list
Out[92]:
In [94]:
data_list[-1]
Out[94]:
In [91]:
def sum_list(data):
# print(data)
if len(data) == 1:
return data[0]
return data[0] + sum_list(data[1:])
sum_list(data_list)
Out[91]:
프로그래밍 연습
회문(palindrome)은 순서를 거꾸로 읽어도 제대로 읽은 것과 같은 단어와 문장을 의미함
회문을 판별할 수 있는 함수를 리스트 슬라이싱을 활용해서 만드세요
회문(palindrome)은 순서를 거꾸로 읽어도 제대로 읽은 것과 같은 단어와 문장을 의미함
회문을 판별할 수 있는 함수를 리스트 슬라이싱을 활용해서 만드세요
참고 - 리스트 슬라이싱 string = 'Dave' string[-1] --> e string[0] --> D string[1:-1] --> av string[:-1] --> Dav
프로그래밍 연습
회문(palindrome)은 순서를 거꾸로 읽어도 제대로 읽은 것과 같은 단어와 문장을 의미함
회문을 판별할 수 있는 함수를 재귀함수를 활용해서 만들어봅니다.
회문(palindrome)은 순서를 거꾸로 읽어도 제대로 읽은 것과 같은 단어와 문장을 의미함
회문을 판별할 수 있는 함수를 재귀함수를 활용해서 만들어봅니다.
In [6]:
def recursive(string):
if len(string) <= 1:
return True
if string[0] == string[-1]:
return recursive(string[1:-1])
else:
return False
print (recursive('ruur'))
프로그래밍 연습
1, 정수 n에 대해 2. n이 홀수이면 3 X n + 1 을 하고, 3. n이 짝수이면 n 을 2로 나눕니다. 4. 이렇게 계속 진행해서 n 이 결국 1이 될 때까지 2와 3의 과정을 반복합니다.
1, 정수 n에 대해 2. n이 홀수이면 3 X n + 1 을 하고, 3. n이 짝수이면 n 을 2로 나눕니다. 4. 이렇게 계속 진행해서 n 이 결국 1이 될 때까지 2와 3의 과정을 반복합니다.
예를 들어 n에 3을 넣으면,
3 10 5 16 8 4 2 1
이 됩니다.
이렇게 정수 n을 입력받아, 위 알고리즘에 의해 1이 되는 과정을 모두 출력하는 함수를 작성하세요.
In [37]:
def func(data):
print (data)
if data == 1:
return
if data % 2 == 0:
return func(int(data / 2))
else:
return func(3 * data + 1)
프로그래밍 연습
문제: 정수 4를 1, 2, 3의 조합으로 나타내는 방법은 다음과 같이 총 7가지가 있음 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 입력으로 주어졌을 때, n을 1, 2, 3의 합으로 나타낼 수 있는 방법의 수를 구하시오
힌트: 정수 n을 만들 수 있는 경우의 수를 리턴하는 함수를 f(n) 이라고 하면,
f(n)은 f(n-1) + f(n-2) + f(n-3) 과 동일하다는 패턴 찾기
출처: ACM-ICPC > Regionals > Asia > Korea > Asia Regional - Taejon 2001
문제 분석을 연습장에 작성해 본 예¶
In [104]:
def f(data):
if data < 0:
return 0
if data == 0:
return 1
elif data == 1:
return 1
elif data == 2:
return 2
elif data == 3:
return 4
return f(data - 1) + f(data - 2) + f(data - 3)
In [37]:
def func(data):
print (data)
if data == 1:
return
if data % 2 == 0:
return func(int(data / 2))
else:
return func(3 * data + 1)
프로그래밍 연습
문제: 정수 4를 1, 2, 3의 조합으로 나타내는 방법은 다음과 같이 총 7가지가 있음 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 입력으로 주어졌을 때, n을 1, 2, 3의 합으로 나타낼 수 있는 방법의 수를 구하시오
힌트: 정수 n을 만들 수 있는 경우의 수를 리턴하는 함수를 f(n) 이라고 하면,
f(n)은 f(n-1) + f(n-2) + f(n-3) 과 동일하다는 패턴 찾기
출처: ACM-ICPC > Regionals > Asia > Korea > Asia Regional - Taejon 2001
문제 분석을 연습장에 작성해 본 예¶
In [104]:
def f(data):
if data < 0:
return 0
if data == 0:
return 1
elif data == 1:
return 1
elif data == 2:
return 2
elif data == 3:
return 4
return f(data - 1) + f(data - 2) + f(data - 3)