Hello Coding 그림으로 개념을 이해하는 알고리즘 Study Note 03
Chapter 3 재귀 (Recursion)
재귀 = 자기 자신을 참조(호출)하는 것 (함수에서 사용 => 재귀 함수)
- 재귀 함수는 자기 자신을 호출하기 때문에 실수를 무한 반복하는 함수를 만들기 쉽다
- 기본 단계(base case) : 함수가 자기 자신을 다시 호출 하지 않는 경우, 무한 반복을 막는 부분
- 재귀 단계(recursion case) : 자기 자신을 호출하는 부분
- 재귀 함수는 기본단계와 재귀 단계 두 부분으로 나누어 작성
- 대표적 예로 팩토리얼이나 피보나치 수열 구현에 사용하는 예시가 있음
장점
- 복잡한 문제를 간결하게 표현
- 수학적인 문제 해결에 유용
단점
- 성능 저하 : 과도한 재귀 호출은 스택 오버플로우를 발생 시켜 프로그램이 비 정상적으로 종료 될 수 있음
- 로직이 잘못된 경우 무한루프에 빠질 수 있음
- 이해하기 어려울 수 있음
스택(Stack)과 호출 스택 (Call Stack)
스택
- 자료구조의 한 종류
- 후입선출 (LIFO Last In First Out), 가장 나중에 추가된 데이터가 가장 먼저 제거되는 구조
- 푸시(Push) : 삽입, 가장 위에 새로운 요소를 추가
- 팝(Pop) : 삭제, 가장 위에 있는 요소를 제거하고 반환
- 피크(Peek) 또는 톱(Top) : 맨위 데이터 조회, 가장 위에있는 요소를 제거하지 않고 반환
- 비어있는지 확인 (IsEmpty) : 스택이 비어있는지 확인
장점
- 간단한 구현, 후입선출(LIFO)의 특성, 재귀적 문제 해결
단점
- 랜덤 엑세스 불가능, 제한된 용도, 오버플로우나 오버헤드가 발생 할 수 있음
사용 예
- 브라우저의 뒤로 가기, Undo 기능, 재귀함수, 괄호 검사(괄호 짝)
호출 스택
- 프로그램에서 실행 중인 함수들의 정보(지역 변수, 매개 변수 등)를 저장하는 스택
- 여러 함수가 서로 호출하며 복잡한 작업을 수행하는데, 호출 스택으로 이를 관리, 제어
- 스택의 LIFO 형태로 인해 함수가 호출 될때 Push 하고, 실행이 완료 되면 Pop 하는 방식으로 동작
- 가장 최근에 호출된 함수가 실행이 완료 되서 종료되면 그 다음 호출된 함수로 돌아감
- 재귀 호출도 호출 스택을 이용해 처리된다
- 디버깅과 에러 처리에도 사용된다
팩토리얼(Factorial)
- 일반적으로 양의 정수에 대해서만 정의됨 (확장된 개념의 감마함수가 있음 참고)
- 0! = 1 로 정의됨 (특수한 경우)
- n! = n x (n-1) x (n-2) x ... x 1
- 예시) 5! = 5x4x3x2x1 = 120
03_factorial.py 팩토리얼 재귀 함수 작성 테스트
Chapter 3 정리
재귀 함수는 자기 자신을 호출 하는 함수, 기본 단계, 재귀 단계가 있다
스택은 FILO 특징이 있고 Push, Pop, Peek(Top) 과 같은 연산이 있다
함수의 호출에는 호출 스택을 사용한다
알고리즘을 작성할 때는 오버플로우와 오버헤드를 조심해야 한다
오버 플로우(Overflow) : 메모리 공간 초과 사용
오버 헤드(Overhead) : 불필요한 추가 적인 시간이나 자원이 사용
댓글
댓글 쓰기