👉 재귀 함수와 재귀 알고리즘 자세히 살펴보기
👉 재귀 함수, 재귀 알고리즘의 예제 자세히 살펴보기
재귀적 : 어떤 사건이 자신을 포함하고 다시 자기 자신을 사용하여 정의
재귀 함수 : 정의 단계에서 자신을 재참조하는 함수
재귀 호출 Recursive call : 자기 자신과 똑같은 함수를 호출하는 것
재귀 알고리즘 Recursive Algorithms : 하나의 함수에서 자기 자신을 다시 호출하여 작업을 수행하는 알고리즘
- 직접 재귀 : 자신과 똑같은 함수를 호출하는 방식
- 간접 재귀 : 다른 함수를 통해 자신과 똑같은 함수를 호출하는 방식
a()가b()를 호출하고, 다시b()가a()를 호출하는 구조 - 순수한 재귀 : 재귀 호출을 여러 번 실행하는 함수
재귀 읽기 (재귀 코드 추론)
- 기저 조건을 찾아, 함수가 어떻게 동작하는지 살핀다.
- 끝에서 두 번째 조건을 찾아, 함수가 어떻게 동작하는지 살핀다
- 위 절차를 반복하고, 그때마다 함수가 어떻게 동작하는지 살핀다.
재귀 알고리즘 분석
- 하향식 방법으로 분석하기 - 문제를 해결하는 새로운 사고 전략 제공
- 상향식 방식으로 분석하기
재귀 알고리즘의 비재귀적 표현
- 꼬리 재귀 제거하를
- 재귀를 제거하기
원리
- 본 문제에서
하위 문제를 찾는다.
(tip) 파라미터로 받은 인풋의 사이즈를 -1 하면 어떻게 될까? 생각해보기 베이스 케이스와재귀 케이스를 정한다.
베이스 케이스 : 하위 문제 없는 빈 리스트나 요소가 1개인 경우
재귀 케이스 : 하위 문제를 찾아야 하는 요소가 2개 이상- 이를 토대로 함수를 구현한다.
# 리스트 뒤집기
def reverse(my_list) :
if len(my_list) <= 1 :
# base case
return my_list
else :
# recursive case
# [5] + [4, 3, 2, 1]
return mylist[-1:] + reverse(my_list[:-1])스택 오버플로우
- 재귀 함수의 경우, 스택 오버플로우 에러를 주의해야 한다.
콜 스택에 함수 호출 위치가 과하게 쌓이는 경우 발생한다.- 즉, 자기 자신을 호출하는 횟수의 한계인
최대 재귀 깊이를 초과하면 발생한다.
재귀 함수 vs 반복문
재귀 함수로 작성한 것들은 반복문을 이용해서 작성할 수도 있다.
다만, ➀ 어떤 문제들은 재귀 함수로 작성하는 게 더 깔끔하고 쉬울 수도 있고, ➁ 반복문으로 구현하게 되더라도 재귀적인 접근 방식으로 해결책을 찾을 수 있기 때문에 재귀 함수가 어려워도 쓰는 경우가 있다.
# 재귀함수
def countdown(n) :
if n > 0 :
print(n)
countdown(n-1)
# 반복문
def countdown(n) :
i = n
while i > 0 :
print(i)
i -= 1재귀 함수 예제
가장 대표적인 문제인 하노이의 탑과 8퀸 문제부터 팩토리얼, 삼각수, 피보나치 수열, 팰린드롬, 자릿수의 합, 리스트의 최댓값 찾기에 관한 자세한 설명은 여기에서 확인 가능하다.
하노이의 탑 Towers of Hanoi
작은 원반이 위에, 큰 원반이 아래에 위치하는 규칙을 지키면서 기둥 3개를 이용해서 원반을 옮기는 문제
# 하노이의 탑
def towers_of_hanoi(no, x, y):
# 원반 no개를 x기둥에서 y기둥으로 옮김
if no > 1 :
towers_of_hanoi(no - 1, x, 6 - x - y)8퀸 문제 8-Queen problem
8개의 퀸이 서로 공격하여 잡을 수 없도록 8*8 체스판에 배치하기 (총 92가지 해결 방법)
- 규칙 1. 각 열에 퀸을 1개만 배치하기
- 규칙 2. 각 행에 퀸을 1개만 배치하기
# 8퀸 문제
pos = [0] * 8 # 각 열에 배치한 퀸의 위치
flag_a = [False] * 8 # 각 행에 퀸을 배치했는지 체크
flag_b = [False] * 15 # 대각선 방향으로 퀸을 배치했는지 체크 (1)
flag_c = [False] * 15 # 대각선 방향으로 퀸을 배치했는지 체크 (2)
# 각 열에 배치한 퀸의 위치 출력
def put() -> None:
for i in range(8):
print('■' if pos[i] == j else '□', end='')
print()
def set(i) -> None:
for j in range(8):
if not flag_a[j] and not flag_b[i+j] and not flag_c[i-j+7]) :
pos[i] = j
if i == 7:
put()
else :
flag_a[j] = flag_b[i+j] = flag_c[i-j+7] = True
flag_a[j] = flag_b[i+j] = flag_c[i-j+7] = False
set(0)팩토리얼 Factorial
n! = 정수 1부터 n까지의 곱
- 팩토리얼은 재귀 함수로 정의하지 않는 것이 오히려 간단하고 효율적이다.
# 팩토리얼 (재귀 함수)
def factorial(n):
if n == 1 :
return 1
else :
return factorial(n-1) * n
def factorial(n):
if n > 0 :
return n * factorial(n-1)
else :
return 1
# 팩토리얼 (반복문)
def factorial(n) :
result = 1
for i in range(n) :
result = result+n
return result삼각수 Triangular number
n번째 삼각수 = 정수 1부터 n까지의 합
# 삼각수
def triangle_number(n):
if n == 1 :
return n
return triangle_number(n-1) + n피보나치 수열 Fibonacci numbers
Fn = n-2항 + n-1항 인 수열 (단, 첫째/둘째 항 = 1)
# 피보나치 수열
def Fn(n):
if n <= 2 :
return 1
return Fn(n-2) + Fn(n-1)팰린드롬 Palindrome
제대로 읽은 것과 거꾸로 읽은 것이 같은 숫자 및 문자열
# 팰린드롬
# 나의 풀이
def is_palindrome(my_str):
if len(my_str) == 1 :
return True
elif len(my_str) == 2 and my_str[0] == my_str[-1] :
return True
elif my_str[0] == my_str[-1] :
return is_palindrome(my_str[1:-1])
return False
# 다른 풀이
def is_palindrome(my_str):
if len(my_str) <= 1:
return True
if my_str[0] != my_str[-1]:
return False
return is_palindrome(my_str[1:-1])거듭제곱 Exponentiation
똑같은 수나 문자열을 여러 번 곱한 것
# 거듭제곱
def power(x, n):
if n == 0 :
return 1
elif n == 1 :
return x
else :
if n % 2 == 0 :
return power(x, n//2) * power(x, n//2)
return x * power(x, n//2) * power(x, n//2)유클리드 호제법 (최대 공약수 구하기)
유클리드 호제법 (Euclidean algorithm)최대 공약수 (GCD, greatest common divisor)
# 유클리드 호제법으로 최대 공약수 구하기
def gcd(x, y):
if y == 0:
return x
else :
return gcd(y, x%y)math.gcd()로 더 간단하게 구할 수도 있다.
자릿수의 합
# 나의 풀이
def sum_each(n):
if len(str(n)) <= 1 :
return n
return int(str(n)[-1]) + int(sum_digits(str(n)[:-1]))
# return int(str(n)[0]) + int(sum_digits(str(n)[1:]))
# 다른 풀이
def sum_each(n):
if n < 10:
return n
return sum_each(n // 10) + (n % 10)리스트의 최댓값 찾기
def max_list(my_list):
if len(my_list) == 1 :
return my_list[0]
max_sublist = max_list(my_list[:-1])
if max_sublist >= my_list[-1]:
return max_sublist
else:
return my_list[-1]👉 재귀 함수와 재귀 알고리즘 자세히 살펴보기
👉 재귀 함수, 재귀 알고리즘의 예제 자세히 살펴보기
planning design development with data