재귀함수(recursion)

재귀함수(recursion)

• 재귀 : 어떤 문제를 해결할 때, 동일한 구조의 더 작은 문제를 해결함으로써 주어진 문제를 해결하는 방법을 재귀라고 합니다.
• 재귀함수 : 재귀적 사고방식을 활용할 수 있게 만든 함수, 함수에서 자신을 다시 호출 하여 작업을 수행하는 방식으로, 주어진 문제를 푸는 방법이다.

재귀함수를 쓰는 이유?

• 변수사용을 줄여주어 오류가 발생할 수 있는 가능성을 줄인다.
• 유지보수가 편리하다.
• 재귀적으로 표현하기 자연스러울 때 코드를 효율적으로 작성하여 가독성이 좋다.

재귀함수 단점

• 느리다! 재귀함수는 반복할때마다 새로 함수를 호출해서 느리다.
  반복문이 오히려 새로 함수를 호출하지않기 때문에 재귀함수보다 속도는 빠르다.
• 재귀함수는 호출할때마다 메모리를 Stack에 저장해야한다.
  이는 선언한 변수의 값만 변경해서 사용하는 반복문과 달리 많은 메모리 사용이 많이 사용한다.

기본 재귀함수 템플릿!

• 재귀의 베이스(base case)
  • 더이상 쪼갤 수 없는 경우, 재귀의 탈출 조건(재귀 호출이 멈추는 조건)
  • 재귀 함수를 만들 때, 언제 재귀를 멈출지 알려주지 않으면 무한 루프에 빠진다.
• 재귀 단계(recursive case)
  • 목표 작업을 위해 재귀의 베이스에 도달할 때까지 이어지는 동작

function recursive(input1, input2, ...) {
  // Base Case : 문제를 더 이상 쪼갤 수 없는 경우
  if (문제를 더 이상 쪼갤 수 없을 경우) {
    return 단순한 문제의 해답;
  }
  // recursive Case
  // 그렇지 않은 경우
  return 더 작은 문제로 새롭게 정의된 문제
  // 예1. someValue + recursive(input1Changed, input2Changed, ...)
  // 예2. someValue * recursive(input1Changed, input2Changed, ...)
}

재귀함수 기본예시)

1부터 num까지의 합을 구하는 방법

• 수도코드 / 기본조건 : num은 0이상의 정수

1. if 문에 base case(재귀의 탈출 조건 / 재귀 호출이 멈추는 조건) 설정
   0 이상의 정수임으로 1보다 작을경우 종료 / 1은 자기자신만있음으로 자기자신을 출력하고 종료
2. 그렇지 않을 경우! recursive case (반복되는 조건)을 설정
   1부터 num까지의 수가 반복적으로 더해지도록 num + Plus(num-1)을 하여 num + num-1씩 한 수를 모두 더해준다.
   ex) num 이 2라면? 2 + 1 = 3

function Plus(num) {

  // Base Case : 문제를 더 이상 쪼갤 수 없는 경우 -> 단순한 문제의 해답
  if(num <= 1) { // 1이면 1을 출력, 1보다 작으면 종료
  return num;
  console.log(num) => 10
  }
  // recursive Case 그렇지 않은 경우 -> 더 작은 문제로 새롭게 정의된 문제
   return num + Plus(num-1)  // 출력한다.
} 

// -> 하나씩 풀이해본다면? num 이 4일 경우
// Plus(num) = num + num-1 + num-2 + num+3 = num
// Plus(num = 4) = 4 + 3 + 2 + 1 = 10
// Plus(num = 3) = 3 + 2 + 1  = 6
// Plus(num = 2) = 2 + 1 = 3
// Plus(num = 1) = 1  //1이되면 1을 리턴
// Plus(num = 0) = 0 //1이되면 0을 리턴

for 반복문으로 작성한다면?

수를 담을 변수를 선언하고 해당 sum 변수에 num까지의 수를 반복적으로 더한다.

function Plus(num){
let sum = 0;

for (let i = 0; i <= num; i++) {
  sum = sum + i;
}
return sum;
console.log(sum) => 10
}

참조
코드스테이츠