[💻 코드스테이츠 FE 44기] 재귀함수

✔️ 시작

재귀 함수에 대해 학습했다.

📍 재귀함수

• 함수가 자기 자신을 호출하는 함수
• 반복문(while, for문)으로 표현할 수 있다.
• 재귀함수를 사용한 알고리즘은 코드의 가독성이 좋다.
• 간단하게 구혆 할 수 있어 유용하다.

재귀 : 원래의 자리로 되돌아 가거나 되돌아 옴
최적화 기법(memoization) : 메모를 하는 것 처럼 값을 기억하고 필요 할 때 재사용

재귀함수 호출이 많아 질 수록 스택 메모리를 많이 사용해 성능 이슈가 발생할 수 있다.

재귀함수를 사용할 때는 적절한 종료 조건과 최적화를 고려해야한다.

function factorial(n) {
	if(n === 0){
    	return 1;
    }else {
    	return n * factorial(n - 1);
    }
}

n이 0인 경우 1를 반환하고, 그러지 않은 경우 n과 factorial(n-1)의 곱을 반환한다.
factorial(n - 1)은 함수 자신을 다시 호출해 n-1에 대한 팩토리얼 값을 계산한다.
=> n인 0이 될 때 까지 반복

언제 재귀함수를 사용하지?

• 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우
• 중첩된 반복문이 많거나 반복문의 중첩 횟수(number of loops)를 예측하기 어려운 경우

재귀적으로 사고하기

• recursice case : 문제를 동일한 방식으로 계속 쪼개기
• base case : 더 이상 안 쪼개면(종료 조건)

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

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

3. 단순한 문제 해결하기

4. 복잡한 문제 해결하기

5. 코드 구현하기

일반적인 재귀 함수 템플릿

function recursive(input1, input2, ...) {
  // base case : 문제를 더 이상 쪼갤 수 없는 경우
  if (문제를 더 이상 쪼갤 수 없을 경우) {
    return 단순한 문제의 해답;
  }

  // recursive case : 그렇지 않은 경우
  return 더 작은 문제로 새롭게 정의된 문제
}

✏️ 마치며

재귀 함수 관련된 알고리즘을 풀었다.
알 듯 하면서도 잘 모르겠다.

반복문으로 하면 금방 푸는데 재귀적으로 하려고 하니 조금 헤맸던 거 같다.