재귀

---

재귀란?

再歸 (두번째 재, 돌아올 귀) : 원래의 자리로 되돌아거가나 되돌아옴.

재귀는 언제 사용되는가?

• 주어진 문제를 비슷한 작은 문제로 쪼개어 풀 수 있는 경우
• 중첩된 반복문이 많은 경우

재귀를 코드로 표현

입력

function recursion () {
  console.log("This is")
  console.log("recursion!")
  recursion()
}

출력

This is
recursion!
This is
recursion!
This is
recursion!
* infinity

무한굴레에서 벗어나며 재귀를 다루는 방법이 있다.
바로 재귀함수를 만드는 것이다

재귀함수

재귀함수를 만드는 방법은 아래와 같다.
1. 재귀함수의 입력값과 출력값 정하기
2. 문제를 쪼개고 경우의 수 나누기
3. 단순한 문제 해결하기(Base case)
4. 복잡한 문제 해결하기(Recursive case)
5. 코드 구현하기

재귀적 사고 연습을 위해 재귀함수를 Base case 와 Recursive case로 나누어보자.

아래는 재귀함수의 기본 타블렛이다.

function recursive(input1, input2, ...) {
    if(문제를 더 쪼갤 수 없는 경우) {    // base case (재귀 탈출 조건)
    	return 단순한 문제의 해답;
    }
    return 더 작은 문제로 새롭게 정의된 문제;	   //recursive case
}

base case는 재귀의 기초, 즉 재귀의 탈출 조건
recursive case는 복잡한 문제를 풀기 위해 작은 문제로 쪼개어 재귀함수를 호출하는 것

아래는 재귀함수를 이용한 피보나치 수열

function fibonacci(num) {
  if(num === 0 || num === 1)
	return num
  return fibonacci(num - 1) + fibonacci(num - 2)
}