JS) 재귀함수

재귀함수

1. 재귀함수

1.1 재귀함수 특징
1.2 재귀함수 사용 예시

---

1. 재귀함수

재귀란? [어떤함수가 스스로를 호출하는것]

• 자료구조에서 Tree구조에서 재귀함수를 사용한다.
• for문과 while문으로도 충분히 할 수 있지만 재귀함수로 풀어야하는 알고리즘은 존재한다.

1.1 재귀함수 특징

특징
1. 종료조건: 종료조건을 통해 원치 않는 값이 들어왔을경우 재귀가 계속 동작하는것을 방지해줍니다.
2. 기반조건(Base case): 재귀함수의 목적으로 if문 내부에 있습니다. 기반조건까지 도달하도록 재귀함수를 구성해보자
3. 재귀: 함수를 재귀하여 기반조건에 도달할때까지 재귀를 실시 해줍니다.

• 재귀함수는 언제 사용하는게 좋을까?

1. 주어진문제를 비슷한구조의 더 작은문제로 나눌수 있을때
2. 중첩횟수의 예측이 어려운경우(다중배열)

arr = [1,2,3,4,5,6]

위 배열의 항목들을 하나씩 더하는 함수를 만들어보겠다.
물론 처음 보는 순간 for문을 먼저 생각할것이다.

function Sumarr(arr) {
  let sum = 0;
  for (let i = 0; i < arr.length; i++) {
    sum += arr[i];
  }
  return sum;
}

위 함수로 충분히 가능하다. 하지만 이 문제를 다른각도로 바라보자

1 + Sumarr([2,3,4,5]) // 1과 나머지 배열
3 + Sumarr([3,4,5]) // 1+2와 나머지 배열
6 + Sumarr([4,5]) //1+2+3과 나머지 배열
10 + Sumarr([5]) //1+2+3+4과 나머지 배열
15 + Sumarr([]) //1+2+3+4+5과 나머지 배열

위 예시를 코드로 구현하면 아래와같다

function arrSum(arr) {
  if(arr.length === 0){return 0}
  // 예외로 빈배열이면 0을 출력한다.
  if(arr.length === 1){
    return arr[0]
  //재귀탈출문으로 배열 길이가 1이면 남은 1배열을 출력한다.
  }
  return arr[0] + arrSum(arr.slice(1))
 //재귀문으로 현재 입력된배열의 첫번째 행과 arrSum에 arr의 1번째 인덱스부터 기입하여 함수를 재귀한다.
}

그림으로 비유하면 위와같다.
끝에 재귀 탈출함수에서 return하는 값에서 역으로 나왔던 수를 더했다.
물론 더 어려운 개념이지만 간단한 문제인만큼 재귀의 역할만 간단히 알아보도록 하자

1.2 재귀함수 사용예시

재귀함수 템플릿

function func(value) {
  if (문제를 더 이상 쪼갤 수 없을 경우) {
    return 단순한 문제의 해답;
  }
  // 그렇지 않은 경우
  return 더 작은 문제로 새롭게 정의된 문제
}

1.2.1

1부터 덧셈하는 함수

function Sumnum(num) {
  if(num === 0){
    return num 
 }
  return num + sumTo(num-1)
}

Ex) Sumnum(4)
return ... 

4 + Sumnum(3)
return 3 + Sumnum(2)
return     2 + Sumnum(1)
return         1 + Snumnum(0)
                    return 0

4 + 3 + 2 + 1 + 0 = 10

1.2.2

배열 순서 뒤집기

function rrA(arr) {
  if(arr.length===0){
    return []
  }
  head = arr.pop()
  tail = arr.slice(0,arr.length)

return [head].concat(rrA(tail))
}

1. arr.length가 0이되면 빈배열을 리턴한다.

2. head에 입력된 배열의 끝 값이 들어간다.

3. tail에 arr의 0번째 인덱스부터 길이만큼 기입합니다.

4. return에 맨 앞에 두었던 head를 앞에 두고 concat사용해 뒤에 tail을 기입하여 현재 함수를 재귀한다.

5. 입력되는 배열의 길이가 0이될시 재귀탈출문을 통해 빈배열을 concat하여 최종적으로 뒤집힌 배열을 출력한다.