고급 정렬 알고리즘엥서 재귀 용법을 사용하므로, 고급 정렬 알고리즘을 익히기 전에 재귀 용법을 먼저 익히기로 합니다.
def factorial(num):
if num > 1:
return num * factorial(num - 1)
else:
return num
# 코드로 검증
for num in range(10):
print (factorial(num))
factorial(n) 은 n - 1 번의 factorial() 함수를 호출해서, 곱셈을 함
시간 복잡도/공간 복잡도는 O(n-1) 이므로 결국, 둘 다 O(n)
# 일반적인 형태1
def function(입력):
if 입력 > 일정값: # 입력이 일정 값 이상이면
return function(입력 - 1) # 입력보다 작은 값
else:
return 일정값 # 재귀 호출 종료
# 일반적인 형태2
def function(입력):
if 입력 <= 일정값: # 입력이 일정 값보다 작으면
return 결과값 # 재귀 호출 종료
function(입력보다 작은 값)
return 결과값
# 일반적인 형태2 로 작성한 팩토리얼
def factorial(num):
if num <= 1:
return num
return_value = num * factorial(num - 1) # return num * factorial(num - 1) 로 작성하는 것도 좋음
return return_value
# 코드로 검증
for num in range(10):
print (factorial(num))
참고: 파이썬에서 재귀 함수는 깊이가(한번에 호출되는...) 1000회 이하가 되어야 함
def muliple(data): if data <= 1: return data return ------------------------- multiple(10)
def multiple(data):
return_value = 1
for index in range(1, data+1):
return_value = return_value * index
return return_value
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)
import random
data = random.sample(range(100), 10)
data
def sum_list(data): if len(data) == 1: return data[0] return -------------------------------- import random data = random.sample(range(100), 10) print (sum_list(data))
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)
data_list
data_list[-1]
def sum_list(data):
# print(data)
if len(data) == 1:
return data[0]
return data[0] + sum_list(data[1:])
sum_list(data_list)
참고 - 리스트 슬라이싱 string = 'Dave' string[-1] --> e string[0] --> D string[1:-1] --> av string[:-1] --> Dav
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'))
예를 들어 n에 3을 넣으면,
3 10 5 16 8 4 2 1이 됩니다.
이렇게 정수 n을 입력받아, 위 알고리즘에 의해 1이 되는 과정을 모두 출력하는 함수를 작성하세요.
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) 이라고 하면,
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)