[코테] 재귀함수
🌱 재귀함수에 대해서 알아보자!
재귀함수란, 자기 자신을 다시 호출하는 함수를 말한다.
말 그대로, 함수가 자기 자신을 반복적으로 부르는 구조라고 할 수 있다!
재귀를 사용하면 코드를 간결하게 표현할 수 있고,
특히 반복적인 구조나 문제를 잘게 쪼개는 상황에서 유용하게 쓰인다.
📌 재귀함수는 언제 고려해야할까?
재귀함수는 다음과 같은 상황에서 고려해볼 수 있다
- 반복적인 계산 구조일 때
- 탐색 범위를 계속 줄여야 할 때
🚨 재귀함수의 핵심: 탈출 조건!
재귀함수를 사용할 때 가장 중요한 건 탈출 조건이다!
자기 자신을 계속 부르다 보면 무한 루프에 빠질 수 있기 때문에,
어디선가 반드시 멈춰야 한다.
이걸 탈출 조건이라고 한다.
팩토리얼 예제로 재귀를 이해해보자!
팩토리얼은 1부터 N까지의 정수를 모두 곱한 값을 말한다.
3!이라면 이렇게 계산된다:
3! = 3 × 2 × 1 = 6연산 하는 방법을 수학적으로 표현하면 아래와 같다!
N! = N × (N-1) × (N-2) ... × 1탐색 범위가 작아지며 반복적인 구조를 가지고 있기에 재귀로 풀면 된다.
재귀에 필요한 정보인 재귀 호출 값, 탈출 조건을 지정해야하며 재귀 호출값은 탐색범위를 줄인 데이터를 넘겨 범위를 줄여 탐색 한다.
- 재귀 호출 값 : N - 1
→ 한 단계 작아진 데이터로 나를 다시 호출한다. - 탈출 조건 : N == 1
→ 더 이상 곱할 게 없을 때 멈춘다.
이를 바탕으로 코드를 작성하면 아래와 같다.
public class Main {
public static void main(String[] args) {
System.out.println("Hello World!");
System.out.println("TEST :: " + solution(3));
}
public static int solution(int n) {
if (n == 1) return 1;
return n * solution(n - 1);
}
}테스트 해보면 3! 인 6이 나오는것을 확인할 수 있다.
회문 예제로 재귀를 이해해보자!
회문이란, 예를 들어 "abcba"처럼
앞에서 읽든, 뒤에서 읽든 똑같은 문자열을 말한다.
쉽게 말해, 종이에 적어놓고 반으로 접었을 때
왼쪽과 오른쪽이 똑같이 생긴 문자열이라고 생각하면 된다!
회문을 어떻게 처리할지 생각해보면,
- 양 끝 문자를 비교해서 같으면 → 남은 안쪽 문자열도 회문인지 확인해보자!
- 이렇게 점점 문자열을 줄여가다 보면 → 결국 비교할 게 없어지거나, 다르거나 중 하나가 된다.
즉, 문자열 양쪽을 잘라가며 반복 확인하는 구조다.
바로 이런 반복적인 패턴과 탐색 범위가 줄어드는 재귀에 딱 맞는 상황이다!
문제 풀기 앞서 재귀에 필요한 재귀 호출값과 탈출 조건을 정리하면 아래와 같다.
- 재귀 호출 값 : s.substring(1, s.length() - 1)
→ 맨 앞과 맨 뒤를 제거한 문자열을 넘긴다. - 탈출 조건 :
- 양 끝이 다르면 return false;→ 더 볼 필요 없이 회문이 아니다
- 문자열의 길이가 0 또는 1이면 return true;
→ 더 비교할 문자가 없으니 회문이다
이를 코드로 나타내면 아래와 같다.
public class Main {
public static void main(String[] args) {
System.out.println("Hello World!");
System.out.println("TEST :: " + solution("abcba"));
}
public static boolean solution(String s) {
if (s.charAt(0) != s.charAt(s.length() - 1)) return false;
if (s.length() <= 1) return true;
return solution(s.substring(1, s.length() - 1));
}
}위 코드 돌려보면 abcba는 앞으로 읽어도 abcba 뒤로 읽어도 abcab 이니 회문으로 true 가 나온다!
끝!