[Algorithm] 재귀 함수

서론

알고리즘 문제 풀 때 재귀로 푸는 건 아는데 머리가 빨리빨리 코드를 생각해 내지 못 하길래
문제를 여러 번 풀어봐야겠다고 생각했다.

재귀 함수란?

어떤 함수 내부에서 자기 자신을 호출 하는 것

• 조건을 만족할 때까지 자기 자신을 호출하는 함수
• 여기서 중요한 것은 조건! 재귀 호출의 탈출 조건이 있어야 함
• 함수의 입력 값과 출력 값에서 항상 꼬이는 것 같다

function recursion (n) {
	if(n <= 0) return 1;
  	else recursion(n-1) + n // 자기 자신 호출
}

• 재귀 함수는 대부분 반복문으로 대체가 가능하다

알고리즘 문제 풀이

• 알고리즘 문제를 예시로 재귀 함수로 구하는 방법과 반목문으로 문제를 푸는 방법 두 가지를 확인해 보자

문제

• 팩토리얼 함수 구현
• 입력값 n에 대하여 n! 구하기

재귀 함수 풀이

function factorial(x) {
  // 재귀 호출 탈출 조건
  if (x === 1) return 1;    
  // 재귀 사용
  return x * factorial(x - 1);
}

예시

• 5!을 구한 다고 했을 때 factorial(5)를 먼저 구해야 한다
• factorial(5)의 반환 값은 5*factorial(4)
• 다음은 factorial(4)의 반환 값을 구하고 반복한다
• 반복한 결과값은 아래 표와 같다

반복문 풀이

• 재귀가 복잡하다면 반복문으로 풀 수 있다
• 사실 재귀가 코드적으로 깔끔하지만 내 기준엔 반복문이 직관적이라 이해하기 편하고 내가 짤 때도 반복문이 복잡하지 않다

let result = 1; 

for (let i = 1; i <= n; i++) {
  result *= i;
}

마무리

이거 하나로 이해할 수가 없고 ㅠㅠ 많이 풀어봐야겠다