서론
드디어 알고리즘 시작이다..
어떤 것부터 시작할까하다가 백준맨인 나는 또 백준 단계별 풀어보기를 하며 알고리즘을 하려고한다
재귀란?
간단하게 말하면 함수가 자기 자신을 호출하는 방식 이라고 볼 수 있다.
큰 규모의 문제를 더 작은 단위로 분할해가며, 반복적으로 해결하는 것이다.
재귀는 기저 조건과 재귀단계라는 두 요소가 존재하는데,
기저조건이란, 재귀 호출을 멈추는 조건
재귀단계란, 자기 자신을 호출하는 과정이다.
이 때, 분할 정복 (divide and conquer) 전략을 많이 사용한다.
재귀함수를 사용하다보면 재귀 함수 == 분할 정복 라고 오해하는 경우가 있는데 이는 맞는 표현은 아니다.
분할 정복이란?
재귀와 분할 정복은 굉장히 연관이 있지만 다른 개념이다.
재귀는 함수가 자기 자신을 호출하는 방법론을 의미한다면 분할 정복은 문제를 나누고 해결한 후 결헙하는 알고리즘 전략이다.
간단한 예시를 들어보자면,,
"시장에 가면" 이라는 게임은 많이 해봤을 것이다.
시장에 가면 사과도 사고
-> 시장에 가면 사과도 사고 배도 사고
-> 시장에 가면 사과도 사고 배도 사고 귤도 사고
즉, 자기 자신을 호출하는 재귀의 형태를 보이지만 분할 -> 정복 -> 병합의 과정은 거치지 않는다.
재귀란 분할 정복을 구현하는 하나의 방법론일 뿐, 이를 대변하는 완전한 정의라고 보기는 어렵다.
작동원리
public static int sum(int n) {
if (n == 1) { // 기저 조건
return 1;
}
return n + sum(n - 1); // 재귀 단계
}해당 코드는 1~n 까지의 합을 게산하는 간단한 재귀함수이다.
만약 5까지의 합을 구한다고 가정하면,
sum(5) 호출 = 5 + sum(4)
sum(4) 호출 = 4 + sum(3)
sum(3) 호출 = 3 + sum(2)
sum(2) 호출 = 2 + sum(1)
sum(1) 호출 = 1 (기저조건 도달)
결국, 5 + 4 + 3 + 2 + 1 = 15의 값을 얻는다.
장점
재귀 함수를 사용함으로 우리는 코드를 간결하게 구현할 수 있다.
특히, 이번에 재귀를 공부하며 풀었던 팩토리얼, 피보나치 수열 등은 반복문 보다 보다 간결하게 구현이 가능하다.
또한 이번에 주로 사용했던 분할 정복, 탐색이나 백트레킹 알고리즘에서 유용하다.
개인적으로는 수학의 개념적 접근에서 유리하다고 보기에 수학 관련 코딩 문제를 해결할 때 그 무엇보다 직관적으로 볼 수 있을 것 같다.
단점
그러나,, 재귀함수에도 단점이 있는데
재귀 호출이 너무 길어지거나 중복적 계산이 많아지는 경우이다.
이 경우 메모이제이션을 활용해야하는데.. 쉽지 않은 것이 현실이다.
문제 추천
재귀함수 문제를 풀고 있다면 해당 문제를 추천한다.
gpt를 돌려도 좋고 답을 제대로 못 구해도 좋다.
그래도 함수 호출의 원리나 과정을 이해하는데 가장 큰 도움이 되는 문제이다.
한번쯤 풀고 넘어가보자!
