오늘 학습 진행 내용
C++
3-1. 재귀함수
재귀함수이해 필요한 자료 구조형
트리 순회
그래프 탐색
D-P
백트랙킹
재귀 호출 단계와 기조 조건으로 나누어 재귀를 설계하는 방법 이해,
간단한 예제를 통해서 재귀 호출 흐름 익힘
반복문과 재귀 함수의 차이(재귀가 유용한 상황)
재귀의 정의
재귀란 자기 자신을 정의하거나 호출하는 것
재귀 함수(recursive call)을 말함 함수가 실행 중 자기 자신을 다시 호출하는 방식
재귀 함수의 요건
재귀 함수 계속 자기 자신 호출하지만 프로그램 종료될 수 있게 설계 필요
재귀 호출 단계
자기 자신을 호출하는 단계
보통 호출할때마다 문제의 크기를 줄여야 함
기저 조건
재귀 함수는 언젠가 종료
특정 조건 충족하면, 더 이상 자기 자신 호출하지 않고 함수 종료
기저 조건 없으면 무한 재귀로 Stack OverFlow 오류 발생
재귀적 사고
재귀 함수로 팩토리얼 구하려면
팩토리얼을 구하는 함수가 이미 있다고 가정
Fact(N)은 N 팩토리얼을 반환하는 함수
현재 문제를 더작은 크기의 문제의 해를 이용해 해결
문제의 크기를 계속 줄여나가다가, 더이상 줄일 수 없는 경우에는 직접 해를 구함.
수학적 귀납법과 재귀의 관계
수학적 귀납법은 도미노 효과와 유사한 개념
첫번째 도미노가 넘어진다(기저 조건)
K 번째 도미노가 넘어지면, K+1번째 도미노가 반드시 넘어짐(재귀 호출 단계)
재귀 함수 동작시 메모리의 모습
함수 호출되면 함수가 동작하는데 필요한 정보들이 메모리에 저장
이때 생성되는 메모리 블록을 스택 프레임이라고 지칭(지역 변수, 매개 변수, 변환 주소 등 정보 포함)
재귀 함수가 반복적으로 호출, 각각의 호출마다 새로운 스택 프레임이 생성되어 스택 메모리에 차곡차곡 쌓임
함수가 종료, 해당 스택 프레임이 제거되며, 이전 호출 상태로 되돌아감
컴퓨터 메모리는 한정된 자원, 재귀함수 호출 시 스택 메모리에 함수 실행 정보 저장, 과도하게 호출 누적되면 스택 오버플로우 발생
반드시 종료 조건 명확히 정의
호출 깊이를 적절히 제한하여 메모리 사용을 관리
재귀를 사용하게 효율적인 경우
스택을 사용하는 경우
함수의 호출 과정은 스택 구조
가장 최근에 호출된 함수부터 가장 먼저 종료되는 LIFO(Last In First Out) 구조
따라서 명시적인 스택 구조 없이도,재귀 호출 통해 스택 기반 알고리즘 구현 가능
깊이 우선 탐색 알고리즘(DFS)
현재 노드를 방문 처리
인접한 노드 중 방문하지 않은 노드를 재귀적 방문
더 이상 방문할 노드가 없으면 이전 노드로 되돌아감
DFS를 구현하면 각 함수는 자신과 인접한 노드만 관리하면 됨
즉 각 노드에서 수행할 작업이 명확하게 분리되므로 코드의 가독성과 유지 보수성 향상
분할 정복 알고리즘
분할 정복 알고리즘은 문제를 작게 나누고 동일한 방법으로 해결한 뒤 결과를 결합하여 전체 문제를 푸는 방식
분할 : 문제를 더 작은 문제로 나눔
정복 : 각 부분 문제를 재귀적으로 해결
결합 : 부분 문제의 해를 합쳐서 원래 문제를 해결
이러한 절차 재귀적 문제 해결하는 과정과 유사
대표적인 예시
병합 정렬
분할 : 현재 배열을 반으로 나눔
정복 : 각 부분 배열을 재귀적으로 병합 정렬
결합 : 정렬된 부분 배열들을 병합하여 하나의 정렬된 배열로 만듬
재귀 사용 시 조심해야 하는 부분
함수는 호출될 때마다 메모리 차지
재귀 함수는 자기 자신을 반복적으로 호출 점점 더 많은 메모리 사용 요구
따라서 재귀 함수 사용 시 함수 과도하게 호출되지 않도록 주의
메모이제이션
재귀함수 중복 호출 줄이는 방식
한번 계산한 결과를 저장하고 다시 계산하지 않는 것
피보나치 수열 절차 동작 과정
fibo(N)이 이미 계산된 값인지 확인
이미 계산된 값이라면, 추가적으로 함수 호출없이 저장된 값 바로 반환
계산되지 않은 값이면, fibo(N-1)+fibo(N-2)를 계산한 뒤 저장하고 그 값을 반환
재귀의 예시(지수 연산)
X의 N승을 반환하는 함수 구현
기저 조건
X의 0승은 1, 이는 수학적 정의 값, 더 이상 쪼갤 수 없는 가장 작은 단위로 반환
재귀 호출 단계
X의 N승을 계산하는 함수
pow(X,N)이 이미 있다고 가정
pow(X,N) = pow(X,N-1)*N
성능 개선 방법
N이 짝수일 경우 효율적으로 계산 방법
pow(X,N) = pow(X,N/2)^2
재귀는 두 가지 핵심 단계로 구성가지 핵심 단계로 구성
기저 조건 : 더 이상 분할되지 않는 종료 조건
재귀 단계 : 자기 자신을 호추랗여 문제를 해결하는 과정
재귀와 반복문 장단점 정리
| 특성 | 재귀 함수 | 반복문 |
|---|---|---|
| 정의 | 함수가 자기 자신을 호출하여 작업을 수행하는 방식입니다. | for, while 등의 제어 구조를 사용하여 작업을 반복 수행하는 방식입니다. |
| 메모리 사용 | 각 함수 호출 시 스택 메모리를 사용하며, 호출이 깊어지면 스택 오버플로우가 발생할 수 있습니다. | 스택 메모리를 사용하지 않으며, 일반적으로 메모리 사용이 효율적입니다. |
| 실행 속도 | 함수 호출과 복귀를 위한 컨텍스트 스위칭으로 인해 반복문보다 느릴 수 있습니다. | 함수 호출 없이 반복을 수행하므로 일반적으로 빠른 실행 속도를 가집니다. |
| 가독성 | 코드가 간결하고, 특히 알고리즘이 재귀적으로 표현되기에 자연스러운 경우 가독성이 높습니다. | 코드 길이가 길어질 수 있으며, 많은 변수를 사용하게 되어 가독성이 떨어질 수 있습니다. |
| 변수 사용 | 상태를 유지하기 위해 추가적인 변수를 사용하지 않아도 되어 코드가 간결해집니다. | 상태 유지를 위해 여러 변수를 사용해야 할 수 있어 코드가 복잡해질 수 있습니다. |
| 무한 반복 시 | 종료 조건을 잘못 설정하면 스택 오버플로우가 발생할 수 있습니다. | 종료 조건을 잘못 설정하면 CPU를 계속 사용하게 되어 시스템에 부하를 줄 수 있습니다. |
사전캠프 퀘스트
선배기수 게임 분석 팀활동 발표 시간 후기
대다수의 팀이 Abyss Diver: Underworld를 선택하여 발표를 진행했으며, 그 외에도 다양한 게임들에 대한 분석 발표가 이어졌다. 선배 기수의 프로젝트 결과물을 살펴보니 전체적으로 완성도가 높고 구조가 짜임새 있게 갖춰진 부분이 많아, 이를 향후 팀 프로젝트의 기준점으로 삼아 참고한다면 큰 도움이 될 것이라고 느꼈다.
발표에서 공통적으로 지적된 문제점으로는 튜토리얼의 부재와 불친절한 게임 설명으로 인한 플레이 난이도 상승이 있었다. 이러한 요소들은 사용자 편의성에 직결되며, 실제 플레이 경험에 예상보다 큰 영향을 미친다는 점을 확인할 수 있었다. 따라서 추후 팀 프로젝트를 진행할 때는 사용자 편의성과 관련된 기능을 우선순위 높게 설정하고, 관련 피드백을 적극적으로 반영하는 것이 바람직하다고 판단된다.
