재귀의 정의

자신을 정의할 때 자기 자신을 재참조하는 방법을 뜻하며, 이를 프로그래밍에 적용한 재귀 호출의 형태로 많이 사용된다.

• 위키백과

언제쓸까?

재귀는 문제의 크기와 상관없이 문제 해결방법이 동일할 경우 적용할 수 있다

ex) 병합정렬

정렬은 문제의 크기와 상관없이 해결방법이 동일하다 ( 큰 데이터는 뒤로, 작은 데이터는 앞으로 )

데이터의 크기를 쪼개고 쪼개서 데이터 크기를 1까지 줄인다

크기가 1인 데이터는 그 자체로 정렬이 되었다고 할 수 있다 ( 문제 해결 )

크기가 1인 문제 (작은 문제해결) 를 풀었으니 다른 크기가 1인 데이터 합쳐서 조금 더 큰 문제를 해결한다 ( 조금 큰 문제 해결)

작은 문제들을 계속 풀어나가다보면 전체 문제 ( 전체 데이터 정렬 )도 해결할 수 있다.

어떻게 생겼을까?

• 재귀 호출이 멈추는 순간

무한 재귀를 이용해서 푸는 문제가 있는지는 모르겠지만 보통의 경우는 재귀가 끝나는 지점을 만들어서 문제를 해결한다. ( 위의 예시에서 데이터의 크기가 1이 되면 재귀 호출을 멈춘다 )

큰 문제들을 작은 문제들로 만들고 그 문제를 더 작은 문제들로 만들고 ..... 그만해!

하다보면 더 이상 작아질 수 없거나 or 개발자가 설정한 범위의 한계까지 다달았을 수 있다.

끝에 왔다면 무조건!! return 을 해주어서 더 이상 재귀가 깊어지지 않게 만들어 준다.

여기서 return 이 되지 못하면 코드가 아래로 내려가서 무한 재귀에 빠진다.

여기서 할 수 있는 작업

하나의 해결책을 찾는 경우 ⇒ return true 를 하고 해당 결과값을 받아 모든 재귀를 끝내는 코드를 작성한다.

모든 해결책을 찾는 경우 ⇒ 재귀 호출만 하지 않으면 알아서 다른 케이스로 이동한다.

특정 작업을 원하는 경우 ⇒ 재귀 밖에서 만든 변수에 담거나 or 인자에 담은 콜백함수를 여기서 실행하면 된다.

• 탈출 조건이 아니네? 더 내려가 보자

재귀 호출을 하기 전에 할 수 있는 동작들이 있다.

1. 현재 단계에서 경우의 수를 나눠서 깊이 들어갈 수 있다 ex) N-Queens 에서 for ( let i = 0; i < col; i++ ) ← 현재 상태에서 경우를 나누는 for문

   

   1-1 위의 그림과 같이 여러 경우의 수를 돌기 위해 필요한 작업이 있다

   for (let i = 0; i < col; i++) {
   	somethingChange();
   	callJegwi(작아진 문제 or 다음 문제를 인자로 넘겨줍니다);
   	resetSomethingChange();
   }
   

   resetSomethingChange() 가 필요한 이유는 뭘까?

   우리는 somethingChage() 를 통해서 '원본'을 건드렸다. 그러면 for 문의 한개의 loop 가 돌고 원본에다가 다른 변화를 줘서 문제를 해결하고 싶은데 resetSomethingChange() 코드가 없다면 더 이상 '원본'이 '원본'이 아닌 상태가 되어버린다. 그렇기 때문에 세분화한 케이스를 다시 돌려서 '원본'으로 만들 필요가 있다.

   1-2 경우의 수를 나누는 방법은 if 문을 통해서 가능하다!