17강 재귀 함수
👉🏻 재귀 함수
- 재귀 함수(Recursive Function)란 자기 자신을 다시 호출하는 함수를 의미한다
- DFS를 실질적으로 구현하고자 할 때 자주 사용되는 방법 중 하나
- 단순한 형태의 재귀 함수 예제
- '재귀 함수를 호출합니다'라는 문자열을 무한히 출력한다
- 어느 정도 출력하다가 최대 재귀 깊이 초과 메시지가 출력된다
- 반복적으로 자기 자신을 호출해서 프린트문을 출력함
- 파이썬에서는 최대 재귀 깊이가 정해져있어
별다른 설정 없이 이런 코드를 실행할 경우 오류 메세지와 함께 프로그램 종료
- 컴퓨터 시스템 상에서 함수가 재귀적으로 호출되면
컴퓨터 시스템의 스택 프레임에 이러한 함수가 반복적으로 쌓여
가장 마지막에 호출된 함수가 처리된 이후 그 함수를 불렀던 함수까지 처리되는 방식
- 이러한 형태가 실제로는 stack과 같은 형태로 동작한다고 이해할 수 있다
- 일종의 stack 자료구조 안에 함수에 대한 정보가 차례대로 담겨서 컴퓨터 메모리에 올라가는 식
- 컴퓨터 메모리는 한정된 크기 만큼의 자원을 가짐
- 무작정 쌓아 올려 호출하게 되면 메모리가 가득차게 됨
- 그래서 재귀 깊이 제한 검
✅ 제한 없이 재귀함수 호출하려면
- 재귀 제한을 느슨하게 만들거나
- 별도로 stack 자료구조를 이용해서, stack 객체를 따로 만들어서 그것을 이용하는 방법을 사용할 수도
- 코테는 일반 재귀함수를 사용해도 통과 가능하게 나옴
- while, for문을 이용하지 않고도 어떤 내용을 반복적으로 수행할 수 있을것
👉🏻 재귀 함수의 종료 조건
- 재귀 함수를 문제 풀이에서 사용할 때는 재귀 함수의 종료 조건을 반드시 명시해야 한다
- 의도적으로 무한 루프를 이용할 것이 아니라면 반드시 종료 조건을 명시해 언젠가는 프로그램이 정해진 값을 반환하도록
- 종료 조건을 제대로 명시하지 않으면 함수가 무한히 호출될 수 있다
- 종료 조건을 포함한 재귀함수 예제
- 1번이 2번을 호출 → 2번이 3번을 호출 ...
- 100번째 재귀함수는 종료 조건에 해당
- 더이상 함수를 호출하지 않고 종료됨
- 99부터 순서대로 종료 → 1번 종료
👉🏻 펙토리얼 구현 예제
- n! = 1 × 2 × 3 × … × (n-1) × n
- 1부터 n까지의 모든 자연수를 차례로 곱한 것
- 수학적으로 0!과 1!의 값은 1이다
- 코드가 더 간결하고 직관적
- 반복문이 사용되지 않음
- 하지만 결과는 같음
👉🏻 최대 공약수 계산 (유클리드 호제법) 예제
- 두 개의 자연수에 대한 최대공약수를 구하는 대표적인 알고리즘으로는 유클리드 호제법이 있다
- 유클리드 호제법
- 두 자연수 A, B에 대하여 (A > B) A를 B로 나눈 나머지를 R이라고 하자
- 이 때 A와 B의 최대공약수는 B와 R의 최대공약수와 같다
- 유클리드 호제법의 아이디어를 그대로 재위함수로 작성할 수 있다
- 예시: GCD(192, 162)
- GCD: Greatest Common Devisor, 최대 공약수
- 함수 동작 과정 상 처음 함수를 호출할 때 a 가 b보다 크지 않아도 괜찮다
👉🏻 재귀 함수 사용의 유의사항
- 재귀 함수를 잘 활용하면 복잡한 알고리즘을 간결하게 작성할 수 있다
- 단, 오히려 다른 사람이 이해하기 어려운 형태의 코드가 될 수도 있으므로 신중하게 사용할것
- 모든 재귀함수는 반복문을 이용해 동일한 기능을 구현할 수 있다.
- 반대도 가능
- 재귀함수가 반복문보다 유리한 경우도 있고 불리한 경우도 있다
- 컴퓨터가 함수를 연속적으로 호출하면 컴퓨터 메모리 내부의 스택 프레임에 쌓인다
- 그래서 스택을 사용해야 할 때 구현상 스택 라이브러리 대신에 재귀 함수를 이용하는 경우가 많다
- DFS를 더 간결하고 작게 작성하기 위해서 재귀함수를 이용해 DFS를 구현한다
출처: https://youtu.be/gFpKGWdEE5g?si=4AElsnrFE3OlvU7Y