2021.09.05

재귀

recursion: 함수 자신을 리턴하는 함수

재귀적 사고 연습?

입력값이나 문제의 순서를 고려하여, 문제를 쪼갤 수 있을 때까지 쪼깬다.

• 가장 작은 쪼갠 부분 ⇒ base case (재귀의 탈출 조건이기도 하다)
• 쪼개지고 남아 있어 base case로 재귀를 사용하는 부분 ⇒ recursive case

모든 재귀는 for 문이나 while 로 구현할 수 있다. \그러나 중첩의 횟수가 감당할 수 없는 정도로 많을 경우, 식이 매우 복잡해 진다.

factorial로 재귀 연습?

수학의 계승(factorial)을 재귀로 연습해 볼 수 있다. 위에 언급처럼 이 문제는 for 문이나 while 로 구현할 수 있지만, 재귀로 풀어보자.

문제) 5!(factorial)의 값?

• 5!은 5 x 4 x 3 x 2 x 1의 값과 같다.
• 5 x 4 x 3 x 2 x 1 = 5 x (4 x 3 x 2 x 1)
• (4 x 3 x 2 x 1) = 4 x (3 x 2 x 1)
• (3 x 2 x 1) = 3 x (2 x 1)
• (2 x 1) = 2 x (1)
• (1)의 값은 무엇인가?

함수(1) ⇒ 1 이다. 쪼갤 수 있는 마지막 케이스이다. 위 식은 재귀함수를 호출하여 값을 구한다.

function fac(num) {
  if (num <= 1) { 
    // num이 1보다 작거나 같을 때 1이 나와야 5 factorial의 마지막 수, 즉 1이 나올 수 있다.
    return 1
	} // 이 식은 base case이며 재귀 탈출을 하도록 한다.
  
  return num * fac(num - 1) 
		// 5 * fac(4)
		// fac(4) = 4 * fac(3)
		// fac(3) = 3 * fac(2)
		// fac(2) = 2 * fac(1)
		// fac(1) = 1

예시 문제 01

러시아 전통인형 마트료시카에 대한 정보를 담은 객체와 수를 입력받아 조건에 맞는 인형이 있는지 여부를 리턴해야 합니다.

입출력

• 입력 1:
  -'matryoshka', 'size' 속성을 갖는 재귀적으로 정의된 객체 (입출력 예시 참고)
  -matryoshka.matryoshka는 null 또는 matryoshka 객체
  -matryoshka.size는 중첩될수록 작아집니다.
• 입력 2:
  number 타입의 수
• 출력:
  boolean 타입

입출력 예시

const matryoshka = {
  size: 10,
  matryoshka: {
    size: 9,
    matryoshka: null,
  },
};

let output = findMatryoshka(matryoshka, 10);
console.log(output); // --> true

output = findMatryoshka(matryoshka, 8);
console.log(output); // --> false

풀이

1) 가장 작게 쪼갤 수 있는 식은 마지막 matryoshka 객체의 size의 값을 찾는 식이다.
1-1) if (matryoshka.size === size) { return true }라는 base case를 정한다.
2) 위의 경우 아닌 경우 내부 객체의 size를 비교하는 재귀 호출을 넣도록 한다. 단, 내부 객체의 값이 존재하고, 찾고자 하는 size가 내부 객체의 size보다 작아야 한다.
2-1) else if (matryoshka.matryoshka && matryoshka.size > size)
{return findMatryoshka(matryoshka.matryoshka, size) 라는 recursive case를 정한다.
3) 위 모든 경우가 아닌 경우, 즉 size나 아무 객체에도 발견되지 않는 경우 false를 반환하도록 한다.
3-1) return false

코드

function findMatryoshka(matryoshka, size) {  
 if (size === matryoshka.size) {
    return true;
  } else if (matryoshka.matryoshka && matryoshka.size > size) {
  return findMatryoshka(matryoshka.matryoshka, size)
}
return