Dot Programming/Java
2022. 4. 10.
[Play with Java] Java 8로 꼬리재귀 함수 만들기 (Tail Recursion)
재귀(recursion)와 반복(iteration) 알고리즘 dp 문제에서 자주 사용하는 방식으로 재귀와 반복이 있다. 보통 Bottom-up방식으로 구현하고 싶으면 반복문을 사용하고, Top-down방식으로 구현하고 싶으면 재귀를 사용하는 경우가 많다. 다음 문제가 나왔을 때 보는 관점에 따라 구현이 달라진다. 예를 들어, 정수 X에 사용할 수 있는 연산이 다음과 같이 세 가지가 있다고 하자. 1. X가 3으로 나누어 떨어지면,3으로 나눈다. 2. X가 2로 나누어 떨어지면, 2로 나눈다. 3. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 구하라. 재귀 (Top-down) 풀이 정수 N → 1로 가는 길이 세 가지 ..