[JS] 재귀함수

나무·2023년 12월 10일
0

재귀함수란?


재귀함수는 자기 자신을 호출하는 함수를 뜻합니다
* 재귀: 원래의 자리로 되돌아가거나 되돌아오는 것을 말한다.

재귀함수를 사용할 때는 꼭 두 경우가 있어야하는데,

  1. base case: 더이상 문제를 쪼갤 필요가 없는 종료된 경우
  2. recursive case: 문제를 쪼개서 풀어가는 경우

e.g

function f(n) {
	if (n <= 1) { // base case
    return 1
    }
  return n + f(n-1) // recursive case
}

참고 자료

재귀함수는 언제 사용하면 좋을까요?

1. 주어진 문제를 비숫한 구조의 더 작은 문제로 나눌 수 있는 경우
2. 중첩된 반복문이 많거나, 반복문의 중첩 횟수를 예측하기 어려운 경우
3. 이 밖에도, 알고리즘 문제의 많은 부분(코테, 알고리즘 테스트, 직무 면접 등)

참고 자료

알고리즘 문제를 활용한 예시를 보자!

콜라 빈명 2개를 가져가면 > 새것 1병으로 교환해준다 나는 총 빈병 20개를 가지고 있다. → 그럼 새것 10병을 받을 것이다.
10병을 그자리에서 마신다 → 그럼 새것 5병을 받을 것이다.
5병을 그자리에서 마신다 → 그럼 새것 2병을 받을 것이다. + 빈병 1개가 남을 것이다.
2병을 그자리에서 마신다  → 그럼 새것 1병을 받을 것이다. 
새병 1개 마셔버리고 + 아까있던 빈병 1개 → 새것 1병을 받을 것이다.
내가 마신 콜라의 총 갯수는 몇 병일까?

  1. 빈명 20개에서 2병당 1개로 교환하는 조건 > 빈병 n개에서 a병당 b개로 교환하는 조건으로 어떤 수를 넣어도 계산해주는 함수를 짜야한다.

    a. while문

    function solution(a,b,n) {
    	let 새콜라 = 0;
      	let 빈병 = n;
      
      while(Math.floor(빈병 / a) > 0) {
      	let 교환한콜라 = Math.floor(빈병 / a)*b;
        빈병 = 교환한콜라 + Math.floor((빈병) % a);
        새콜라 += 교환한콜라;
      }
      return 새콜라
    }

    b. 재귀함수

    1. 베이스 조건 만들기
    2. 리턴 타입을 확인하기
    3. 베이스 조건에 가까워질 수 있도록 매개변수의 값을 서서히 줄이면서 연산하기
    4. 한단계 위, 3단계 위 정도까지 값이 잘 돌아가는지 테스트 해보기

    함수자체가 크게 반복문의 역할을 한다
    베이스 조건 만들기리턴 타입 확인하기
    if문으로 베이스조건(종료 조건)을 먼저 지정하고, 종료 조건에 도달하면 계산 완료된 새콜라의 갯수(리턴 타입)을 반환하면서 함수가 종료된다

    베이스 조건에 가까워질 수 있도록 매개변수의 값을 서서히 줄이면서 연산하기
    교환한 콜라와 빈병, 새콜라의 계산식은 while 문과 똑같다
    종료 조건에 도달할 수 있도록 빈병이 점차 줄어들 것이고,
    리턴을 할 때 줄어든 빈병을 매개변수로 넣고 다시 재귀함수를 호출한다

    let 새콜라 = 0;
    
    function recursive(a, b, 빈병) {
    	if(빈병 < a) {
        	return 새콜라; 
        } // 베이스 조건(종료 조건)
      
      let 교환한콜라 = Math.floor(빈병 / a) * b;
      빈병 = 교환한콜라 + Math.floor((빈병) % a);
      새콜라 += 교환한콜라;
      return resursive(a, b, 빈병);
    }

return recursive(a, b, n)

```

참고 자료

profile
🌳

0개의 댓글