재귀함수

재귀는 주어진 문제를 더 작은 단위로 쪼갤수있을때, 중첩된 반복문의 횟수를 예측하기 어려울때 많이쓰인다.

모든 재귀함수는 반복문으로 표현이 가능하다.

 

재귀적 사고를 하는법.

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

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

3. 단순한 문제해결하기

4. 복잡한 문제해결하기 

5. 코드구현하기

 

 

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

입력

인자 1 : matryoshka

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

인자 2 : size

• number 타입의 수

출력

• boolean 타입을 리턴해야 합니다.

주의 사항

• 함수 findMatryoshka는 재귀함수의 형태로 작성합니다.
• 반복문(for, while) 사용은 금지됩니다.
• 입력받은 객체는 함수의 호출 뒤에도 처음 상태를 유지해야 합니다(immutability).
• 빈 객체를 입력받은 경우, false를 리턴해야 합니다.

입출력 예시

처음 풀었을때 풀이가 틀렸던 점

 

: else if 절안에 matryoshka.matryoshka를 써주지않았다. 

matryoshka.matryoshka가 존재해야 matryoshka를 까보고 확인할수있기에 필수조건이다. 

function findMatryoshka(matryoshka,size){
//결과는 불린값으로 트루/ 펄스
//단순한문제 : 사이즈가 같다면 사실이다. 
	if(matryoshka.size === size){
		return true;
     }else if(matryoshka.matryoshka && matryoshka.size > size){
		return findMatryoshka(matryoshka.matryoshka,size)
    }
    
    return false;

}