재귀의 이해

재귀의 개념

• 재귀(再歸) : 원래의 자리로 되돌아가거나 되돌아옴.
  
  
• 함수를 호출하면 어떻게 될까요?
  
• recursion 함수를 호출했더니, 자기 자신을 끝없이 호출하면서 같은 코드가 계속해서 실행되는 것을 볼 수 있습니다. 이 recursion 함수처럼 자기 자신을 호출하는 함수를 재귀 함수라고 합니다. 재귀 함수를 잘 활용하면 반복적인 작업을 해야하는 문제를 좀 더 간결한 코드로 풀어낼 수 있습니다.

재귀로 문제 해결하기

• 문제: 자연수로 이루어진 리스트(배열)를 입력받고, 리스트의 합을 리턴하는 함수 arrSum 을 작성하세요.

1. 문제를 좀 더 작게 쪼갭니다.
2. 1번과 같은 방식으로, 문제가 더는 작아지지 않을 때까지, 가장 작은 단위로 문제를 쪼갭니다.
3. 가장 작은 단위의 문제를 풂으로써 전체 문제를 해결합니다.

1.문제를 작게 쪼개기

• 단순하게 생각해보면, 배열의 합을 구할 때 [1, 2, 3, 4, 5] 의 합을 구하는 것보다 [2, 3, 4, 5] 의 합을 구하는 것이 더 작은 문제이고, 여기서 또 [2, 3, 4, 5] 의 합을 구하는 것보다 [3, 4, 5] 의 합을 구하는 것이 더 작은 문제일 것입니다.
  

2.문제를 가장 작은 단위로 쪼개기

• 위에서 문제를 쪼갠 방식을 반복해서 문제를 계속해서 쪼개면 더이상 쪼갤 수 없는 상태에 도달하게 됩니다.

3.문제 해결하기

• 2번에서 도달한 가장 작은 문제는 arrSum([]) 이었습니다. 빈 배열의 합은 0이므로, 0을 리턴해주면 되겠죠? 이렇게 가장 작은 문제를 해결하는 순간, 아래 코드처럼 쪼개졌던 문제가 거꾸로 거슬러 올라가면서 합쳐지게 됩니다.
  
  
• 재귀로 문제가 쪼개어지는 과정
• arrSum 함수가 내부에서 arrSum 함수를 호출하면서 문제가 쪼개어져 나가고, 결국 문제를 더이상 쪼갤 수 없는 arrSum([]) 까지 함수가 호출되는 것을 볼 수 있습니다.
  
• 재귀로 문제가 해결되는 과정
• arrSum([]) 는 조건문에 의해 더이상 자기자신을 호출하지 않고, 숫자 0을 리턴하면서 종료됩니다. 그 결과 중첩되어있던 함수들도 연쇄적으로 숫자를 리턴하고, 최종적으로는 배열의 모든 요소의 합을 리턴하면서 문제가 해결됩니다.

재귀는 언제 사용하는 게 좋을까?

1. 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우
2. 중첩된 반복문이 많거나 반복문의 중첩 횟수(number of loops)를 예측하기 어려운 경우

재귀의 활용

Guide : 재귀적으로 사고하기

1.재귀 함수의 입력값과 출력값 정의하기

• 재귀적으로 사고하는 데에 가장 먼저 해야 할 일은 문제를 가장 추상적으로 또는, 가장 단순하게 정의하는 것입니다.
• 함수 arrSum 의 경우 number 타입을 요소로 갖는 배열을 입력으로 받고, number 타입을 리턴합니다.
  - arrSum: [number] => number ← 입출력값 정의

2. 문제를 쪼개고 경우의 수를 나누기

• 문제를 쪼갤 기준을 정하고, 정한 기준에 따라 문제를 더 큰 경우와 작은 경우로 구분할 수 있는지 확인합니다.
• 중요한 관점은 입력값이나 문제의 순서와 크기입니다.
• 함수 arrSum은 입력값이 빈 배열인 경우와 그렇지 않은 경우로 나눌 수 있습니다. 각각의 경우는 다른 방식으로 처리해야 합니다.
  - arrSum: [number] => number
  • arrSum([ ]) ← 입력값이 빈 배열인 경우
  • arrSum([요소1, 요소2, ... , 요소n]) ← 그렇지 않은 경우

3.단순한 문제 해결하기

• 재귀의 기초(base case) => 나중에 재귀 함수를 구현할 때, 재귀의 탈출 조건(재귀 호출이 멈추는 조건)을 구성합니다.
• 탈출 조건이 없는 경우 재귀 함수는 끝없이 자기 자신을 호출하게 됩니다.
• 문제를 덜 쪼갠 상태에서 탈출 조건을 세우는 경우 문제를 제대로 해결할 수 없게 됩니다.
• 문제를 최대한 작게 쪼갠 후에 문제를 해결하는 것이 중요합니다.
• 함수 arrSum 을 더이상 쪼갤 수 없는 경우는 입력값이 빈 배열일 경우이고, 이때 arrSum([]) 의 리턴값은 0입니다.
  - arrSum: [number] => number
  • arrSum([ ]) === 0 ← 입력값이 빈 배열인 경우 : 해결!
  • arrSum([요소1, 요소2, ... , 요소n])

4.복잡한 문제 해결하기

• 길이가 1 이상인 배열이 함수 arrSum 에 입력된 경우, 입력된 배열을 배열의 첫 요소와 나머지 요소를 입력값으로 갖는 문제로 쪼개고, 둘을 더합니다.
• arrSum: [number] => number
• arrSum([ ]) === 0
• arrSum([요소1, 요소2, ... , 요소n]) === 요소1 + arrSum([요소2, ..., 요소n]) ← 그렇지 않은 경우 : 해결!
• 배열을 첫 요소와 더 작은 문제로 쪼개는 방법만 안다면, 함수 arrSum 을 재귀적으로 구현할 수 있습니다.

5. 코드 구현하기