Code States 26일차 - 재귀

"재귀"란 무엇일까

동일한 구조의 더 작은 문제를 해결함으로써 주어진 문제를 해결하는 방법을 재귀(recursion)라고 한다.

 

설명을 추가하기 위해 JAVASCRIPT.INFO에서 가져온 재귀에 대한 설명이다.

재귀는 큰 목표 작업 하나를 동일하면서 간단한 작업 여러 개로 나눌 수 있을 때 유용한 프로그래밍 패턴이다. 목표 작업을 간단한 동작 하나와 목표 작업을 변형한 작업으로 단순화시킬 수 있을 때도 재귀를 사용할 수 있다. 특정 자료구조를 다뤄야 할 때도 재귀가 사용된다.

문제 해결을 하다 보면 함수에서 다른 함수를 호출해야 할 때가 있다. 이때 함수가 자기 자신을 호출할 수도 있는데, 이를 재귀라고 부른다.

재귀와 스택

결론은 모르겠다. 글을 쓴 곳마다 의미가 다르다. 그냥 알기만 하고 넘어가도록하자.

 

모든 재귀 함수는 반복문(while 문 또는 for 문)으로 표현할 수 있다. 그러나 재귀를 적용할 수 있는 대부분의 경우에는, 재귀를 적용한 코드가 더욱 간결하고 이해하기 쉽다. 사실 모든 재귀 함수는 재귀 호출 없이 while / for loop으로 표현이 가능합니다.

---

재귀적으로 사고하기

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

재귀 함수를 통해 풀고자 하는 문제, 즉 도달하고자 하는 목표를 정의하는 데 도움이 된다. 재귀적으로 사고하는 데에 가장 먼저 해야 할 일은 문제를 가자 ㅇ추상적으로 또는, 가장 단순하게 정이하는 것이다.

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

주어진 문제를 어떻게 쪼갤 것인지 고민한다. 문제를 쪼갤 기준을 정하고, 정한 기준에 따라 문제를 더 큰 경우와 작은 경우로 구분할 수 있는지 확인한다. 일반적인 경우, 입력값으로 기준을 정한다. 이때 중요한 관점은 입력값이나 문제의 순서와 크기이다. 주어진 입력값 또는 문제 사아황을 크기로 구분할 수 있거나, 순서를 명확하게 정할수 있다면 문제를 구분하는 데 도움이 된다. 그리고 구분된 문제를 푸는 방식이 순서나 크기에 관계 없이 모두 같다면, 문제를 제대로 구문한 것이다.

3. 단순한 문제 해결하기

문제를 여러 경우로 구분한 다음에 가장 해결하기 쉬운 문제부터 해결한다. 이를 재귀의 기초(base case)라고 한다. 재귀의 기초는 나중에 재귀 함수를 구현할 때, 재귀의 탈출 조건(재귀 호출이 멈추는 조건)을 구성한다.

4.복잡한 문제 해결하기

남아있는 복잡한 경우를 해결한다.

5. 코드 구현하기

일반적인 재귀 함수의 템플릿이다. 재귀 함수 연습에 활용하자.

function recursive(input1, input2, ...){
  // Base Case : 문제를 더 이상 쪼갤 수 없는 경우
  if(문제를 더이상 쪼갤 수 없을 경우){
    return 단순한 문제의 해답;
  }
  // revursive Case
  //그렇지 않은 경우
  return 더 작은 문제로 새롭게 정의된 문제;
}

---

결국은 반복문 대신 똑같은 함수를 불러와 반복한다는 의미이다. 이게 맞나 싶지만 처음에 나온 링크를 통해 더 공부하자!