728x90
학습 내용
- 코딩테스트에서 자주 등장하는 DFS/BFS를 이해하기 전 재귀에 대해 알아보고자 한다
- 내가 이해할 수 있을 만큼 쉽게 설명해보고자 한다
재귀
- 자기 자신을 다시 호출하는 함수
재귀함수 예제
팩토리얼 예제
# 반복적으로 구현한 n!
def factorial_iterative(n):
result = 1
# 1부터 n까지의 수를 차례대로 곱하기
for i in range(1, n+1):
result *= i
return result
# 재귀적으로 구현한 n!
def factorial_recursive(n):
if n <= 1: # n이 1이하인 경우 1을 반환
return 1
# n! = n * (n-1)!를 그대로 코드로 작성하기
return n * factorial_recursive(n-1)
# 각각의 방식으로 구현한 n! 출력(n = 5)
print('반복적으로 구현 : ', factorial_iterative(5))
print('재귀적으로 구현 : ', factorial_recursive(5))
최대 공약수 계산 (유클리드 호제법) 예제
- 유클리드 호제법
- 두 자연수 A, B에 대하여 (A > B) A를 B로 나눈 나머지를 R이라고 하자
- 이때 A와 B의 최대공약수는 B와 R의 최대공약수와 같다
- 이를 그대로 재귀 함수로 작성할 수 있다
def gcd(a, b);
if a % b == 0:
return b
else:
return gcd(b, a%b)
print(gcd(192, 162)) # 6이 출력됨
유의 사항
- 재귀 함수를 잘 활용하면 복잡한 알고리즘을 간결하게 작성할 수 있음
- 오히려 다른 사람이 이해하기 어려운 형태의 코드가 될 수도 있으므로 신중하게 사용해야 함
- 모든 재귀 함수는 반복문을 이용하여 동일한 기능을 구현이 가능하다
- 재귀 함수가 반복문보다 유리한 경우도 있고 불리한 경우도 있음!
- 컴퓨터가 함수를 연속적으로 호출하면 컴퓨터 메모리 내부의 스택 프레임에 쌓이므로 스택을 사용해야 할 때 구현상 스택 라이브러리 대신에 재귀 함수를 이용하는 경우가 많음
총평
- 이렇게 또 공부하면 이해되는데 막상 풀이할 때는 어려운 것 같다
- 일단 이정도로 정리를 마치고 더 필요하면 추가 해야겠다.
출처
이것이 코딩 테스트다 교재/강의
https://www.youtube.com/watch?v=7C9RgOcvkvo
728x90
'PYTHON > 개념정리' 카테고리의 다른 글
정렬 (0) | 2024.05.09 |
---|---|
[Greedy] 그리디 (0) | 2024.05.09 |
[DFS/BFS] DFS, BFS (0) | 2024.05.09 |