while 반복문 -> 재귀함수 변환
while 반복문을 재귀함수로 변경하여 에러시 재입력받도록 try/catch
📜 제목으로 보기
반복문(while) to 재귀
01 while문 내부 전체로직을 1개메서드로 추출
public void run() {
final PairProgram pairProgram = new PairProgram();
while (!pairProgram.isOff()) {
final Menu menu = Menu.from(inputView.inputMenu());
menu.execute(inputView, outputView, pairProgram);
}
}
public void run() {
final PairProgram pairProgram = new PairProgram();
while (!pairProgram.isOff()) {
start(pairProgram);
}
}
private void start(final PairProgram pairProgram) {
final Menu menu = Menu.from(inputView.inputMenu());
menu.execute(inputView, outputView, pairProgram);
}
02 while문을 벗겨내고, 반복되도록 마지막에 한번더 호출한다.(필요연산이 있다면, 재귀함수 파라미터 속에서 변수와 함께)
public void run() {
final PairProgram pairProgram = new PairProgram();
// while (!pairProgram.isOff()) {
start(pairProgram);
// }
}
private void start(final PairProgram pairProgram) {
final Menu menu = Menu.from(inputView.inputMenu());
menu.execute(inputView, outputView, pairProgram);
start(pairProgram);
}
03 while문의 ! 탈출조건을 -> 재귀함수 맨위의 종착역으로서 if 탈출조건 early return;으로 지정해준다.
public void run() {
final PairProgram pairProgram = new PairProgram();
// while (!pairProgram.isOff()) {
start(pairProgram);
// }
}
private void start(final PairProgram pairProgram) {
if (pairProgram.isOff()) {
return;
}
final Menu menu = Menu.from(inputView.inputMenu());
menu.execute(inputView, outputView, pairProgram);
start(pairProgram);
}
04 에러발생시 다시시작하고 싶은 부분(입력부분)부터 try{}로 째려보게 한다. -> 에러안나도 재귀함수는 flag에 걸리기전까지 반복해야하므로 재귀호출부까지 다 째려본다
private void start(final PairProgram pairProgram) {
if (pairProgram.isOff()) {
return;
}
try {
final Menu menu = Menu.from(inputView.inputMenu());
menu.execute(inputView, outputView, pairProgram);
start(pairProgram);
} catch (Exception e) {
System.out.println("[ERROR]" + e.getMessage());
start(pairProgram);
}
}
꼬리재귀
재귀 사용 이유
- 반복문보다
가독성이 좋다- f(n) = f(n - 1) + f(n - 2) ) : f(n)을 구하기 위해선 f(n - 1), f(n - 2)라는 자기자신의 함수를 인자만 바꾸고 다시 호출해야 한다.
- 변수가 줄어들어 -> 사이드이펙트가 줄어든다.
- 가독성 = 유지보수비용 > 성능유지비용
- 꼬리재귀를 사용하면, 단점인 스택오버플로우를 방지할 수 있다.
- 실행할 작업을 없애 함수 호출 위치를 저장하지 않도록하여 스택이 넘치는 경우를 방지
- 파일 옵션에서 코드 최적화가 되도록 설정해 주어야 한다.
- 꼬리 재귀는 결국 반복문 실행이기 때문에 일반 재귀 함수에서 발생하는 스택 오버 플로우나 성능저하가 발생하지 않는다.
-
연산을 재귀함수의 인자에서만시행하여- 재귀의 업데이트되는 상태변수(count, n)의 시작값 뿐만 아니라 누적연산 등 연산의 초기값도 같이 가져간다.
재귀 작성법
-
base case를
input을 0 또는1과 관련지어서 생각한다.-
문제에서 주어진 요구사항 및 예시를 무시하고 0 또는 1과 관련지어서 생각하자
- 예시로 주어진 인풋값을 보고, 어떻게 이걸 답으로 만들지? 라고 생각하면 안 된다. 자꾸 함수 실행 순서를 생각하게 되기 때문이다.
- 최대한 재귀적으로 생각하지 않고, 마치 1차원 문제인 것처럼 푸는 게 우리 전략이다.
이 때 가장 간단한 인풋값은 0 혹은 1인 경우가 많다. 만약 정수 타입이 들어온다면, 인풋이 0이나 1인 상황을 생각해보자. 만약 배열이 들어온다면? 그러면 배열의 길이가 0인 경우(빈 배열), 배열의 길이가 1인 경우를 생각해보자. 만약 트리가 들어온다면? 인풋값이 nil인 경우, 혹은 자식 노드가 nil(잎 노드)인 경우를 생각해보자. 만약 인풋값이 2차원이라면? 인풋값이 m x n 그리드 (이차원 배열)이라면, 둘 다 0이거나 (m = 0, n = 0), 둘 중 하나가 1이거나 (m = 0, n = 1) (m = 1, n = 0) 둘 다 1인 (m=1, n=1) 케이스를 생각해보자. 0과 1을 사용한 인풋값이 들어왔을 때 즉각 답을 구할 수 있는가? 만약 YES라면, 그게 베이스 조건과, 베이스 조건에서의 결과값이 된다.
-
꼬리재귀 연습
public class MyTest {
//https://velog.io/@eddy_song/you-can-solve-recursion
@DisplayName("")
@Test
void for_loop() {
int sum = 0;
// 0부터 100까지 누적합
for (int i = 0; i <= 100; i++) {
sum += i;
}
System.out.println("sum = " + sum);
}
@DisplayName("")
@Test
void recursive() {
//1. 재귀함수는 일단 메서드를 호출해서 실행하므로, 메서드부터 만든다.
// -> 기본적으로 인자는 시행횟수가 들어가서 +1, -1, /2 등으로 업데이트되서 다음 재귀를 호출한다.
System.out.println("recursiveSum(100) = " + recursiveSum(100));
}
private int recursiveSum(final int n) {
//1. 줄어들면서, input과 0과 1과 관련시켜 가장 간단한 base case를 찾아 문제를 풀어 return하기
// 0 -> 0까지의 합 return 0
// 1 -> 1까지의 합 return 0 + 1
// 2 -> return 0 + 1 + 2
//2. base값에 가까운 윗단계로 input값 조정 후 input(n)과 관련지어 계산하기
// 3 -> 0 + 1 + 2 + 3 = f(2) + n
// 0 + 1 까지의 합에서 base는 n=0이 들어오는 경우이다.
if (n == 0) {
return 0;
}
return recursiveSum(n - 1) + n;
}
@DisplayName("")
@Test
void recursive_to_tail() {
// recursiveSumByTail(100);
//1. 연산(덧셈)의 초기값(0) 또한 파라미터로 건네주어, 인자내에서 연산 후 다음 재귀의 초기값으로 호출되게 한다.
System.out.println("recursiveSumByTail(100, 0) = " + recursiveSumByTail(100, 0));
}
private int recursiveSumByTail(final int n, final int acc) {
//2. 종착역에서 반환값이 있었다면, 꼬리재귀에서는 해당재귀호출()자체가 최종 값이 되므로
// -> 최종값이 아니라-> 연산의 결과 파라미터를 찍어주면 된다.
// -> 종착역에서 연산이 이루어지지 않고 [return 연산변수]로 끝나기 때문에, 종착역을 마지막연산n보다 1개 더갔을 때 연산변수를 반환하도록 한다.
// if (n == 0) {
// return 0;
// return acc;
// }
// 종착역을 최종연산지점보다 1개 더 주어서 걸리게하고, 직전까지의 계산 = n최종지점까지의연산 의 결과인 acc를 return한다.
if (n < 0) {
return acc;
}
return recursiveSumByTail(n - 1, acc + n);
}
@DisplayName("")
@Test
void zero_to_100_sum_by_tail() {
//1. 꼬리재귀는 [횟수관련 초기값] + [연산관련 초기값] 모두를 가지고 들어간다.
// - 0부터 시작하고, 덧셈의 초기값은 0이다
System.out.println("recursiveSumReverse(0, 0) = " + recursiveSumReverse(0, 0));
}
private int recursiveSumReverse(final int count, final int acc) {
//2. basecase는 0,1과 관련지어서 input을 만들어 풀어주는데, 여기서 종착역은 99, 100이다.
// -> 꼬리재귀에서는 종착역을 최종지점(100)을 1단계 넘어서 지정해준다.
// -> 직전까지 = 최종지점(100)까지의 [파라미터에서 연산]한 결과물이 [오버지점 파라미터]로 들어왔을 것이니까 그것을 반환해준다.
if (count > 100) {
return acc;
}
//3. 횟수변수 및 연산변수를 [파라미터에서 연산 하여 업데이트]해준다.
// -> 직전까지의 연산값 acc를 현재n번째 (count) 와 관련시켜 연산해주면 된다.
return recursiveSumReverse(count + 1, acc + count);
}
}