재귀함수 선언시 뜨는 에러에 대한 생각

이전의 동전교환 문제를 풀며 해당 로직을 구현하였다

private static void dfs(int cnt, int sum) {
        if(total <= cnt) return;
        if(sum > m) return;
        if(sum == m) {
            total = Math.min(total,cnt);
        } else {
            for(int i=0; i<n; i++) {
                dfs(cnt+1, sum+coins[i]);
            }
        }
    }

여기서 for문을 선언할때 처음에는 이런 구조로 선언을 했다

for(int i=0; i<n; i++) {
    sum+=coins[i];
    dfs(cnt+1, sum);
}

겉보기에는 이상이 없어보이지만 해당 코드를 실행하면 이상한 값이 나온다
(편의상 내림차순을 없앴습니다)

• 정상적일때
  cnt : 13, sum : 13, total : 500
  cnt : 14, sum : 14, total : 500
  cnt : 15, sum : 15, total : 500
  cnt : 15, sum : 16, total : 15
  cnt : 15, sum : 19, total : 15
  cnt : 14, sum : 15, total : 15
  cnt : 14, sum : 18, total : 14
  cnt : 13, sum : 14, total : 14
  cnt : 14, sum : 15, total : 14

  total : 3
  

• 이상한 구조 사용시
  cnt : 13, sum : 13, total : 500
  cnt : 14, sum : 14, total : 500
  cnt : 15, sum : 15, total : 500
  cnt : 15, sum : 17, total : 15
  cnt : 15, sum : 22, total : 15
  cnt : 14, sum : 16, total : 15
  cnt : 14, sum : 21, total : 15
  cnt : 13, sum : 15, total : 15
  cnt : 13, sum : 20, total : 13
  cnt : 12, sum : 14, total : 13

  total : 4

내용을 보면 알 수 있듯이 sum이 이상하게 나온다
그래서 그 이유를 찾아본 결과

정답인 코드는 함수를 선언하면서 값을 더하게 된다
그리고 그 값이 다음 함수에서 쓰인다
만약 바로 리턴이 될 경우 그 값은 함수선언문 안에서 쓰였기때문에 사라지게된다
다시 코드를 보자

for(int i=0; i<n; i++) {
	//sum : 1
    dfs(cnt+1, sum+coin[i]);
    //이때 이 dfs함수로 넘어가 sum : 2가 되었다.
    //하지만 바로 리턴이 될경우 다시 1로 돌아간다
    //sum : 1
}

이렇게 정상적으로 동작한다
하지만 내가 작성한 코드를 보면

for(int i=0; i<n; i++) {
	//sum : 1
    sum+=coin[i];
    //sum : 2
    dfs(cnt+1, sum);
    //이때 이 dfs함수로 넘어가 sum : 2가 되었다.
    //여기서 바로 리턴이 될경우 sum은 이전 dfs에서 2가 되었기때문에 계속 2이다
    //sum : 2
    //문제발생
}

sum을 이전 dfs문에서 더했기때문에 그 dfs에 영향을 끼치고 에러로 이어지게 된다

결론 : 재귀를 이용할때 덧셈의 경우 리턴이 된 다음의 경우도 생각해보자