재귀함수

재귀함수란 무엇일까?

재귀함수는 함수 내부에서 자신을 호출하고, 그 함수 내부에서 또 자신을 호출하는 아래의 그림과 같은 구조를 가진다.

👉 재귀함수는 자기 자신을 호출하는 함수를 뜻하며, 기본적으로 아래와 같은 구조를 가진다.

function recursion () {
  console.log("recursion 함수가 실행되었습니다.")
  recursion() // 자기 자신을 호출한다.
}
``

recursion 함수가 실행되었습니다.
recursion 함수가 실행되었습니다.
recursion 함수가 실행되었습니다.
...

하지만 위와 같은 구조로 작성할 경우 무한으로 자기 자신을 호출하여, stackoverflow를 발생시킨다. 따라서 if문과 같은 조건을 걸어서 빠져나올 구간을 만들어 주어야 한다.

function recursion (num) {
  console.log(num + "번 recursion 함수가 실행되었습니다.")
  // num이 3이 되면 종료한다.
  if(num === 3) { 
  	return;
  }
  recursion(num + 1) // 자기 자신을 호출한다.
}

1번 recursion 함수가 실행되었습니다.
2번 recursion 함수가 실행되었습니다.
3번 recursion 함수가 실행되었습니다.

👉 재귀함수에서 자기 자신을 호출하는 것은 recursive case이다.
👉 재귀함수에서 탈출 조건에 걸려 return 되는것은 base case이다.

재귀를 사용한 예시

// giftBox 배열 안에 wish라는 요소가
// 존재한다면 true를 반환
// 존재하지 않는다면 false를 반환
function unpackGiftbox(giftBox, wish) {
  // giftBox의 각 요소를 순환
  for(let i = 0; i < giftBox.length; i++){
    // 만약 giftBox[i]의 요소가 wish와 같다면 true를 반환
    if(giftBox[i] === wish){ return true; }
    // 만약 giftBox[i]의 요소가 배열이라면
    if(Array.isArray(giftBox[i])){
      // unpackGiftbox(giftBox[i], wish)함수를 func에 할당한다.
      const func = unpackGiftbox(giftBox[i], wish);
      // 만약에 unpackGiftbox(giftBox[i], wish)함수를 할당한 func가 참이라면
      // true를 반환한다.
      if(func){ return true;}
    }
  }
  return false;
}

입력

let arr = ['macbook', ['eyephone', [], ['postcard']], 'iphone']
unpackGiftbox(arr, 'iphone') // true를 반환

재귀를 사용하는 상황

• Tree, Graph(자료구조)를 순회할 경우 - dfs(트리 순회 방법)
• 정해진 알고리즘을 작성할 경우

재귀를 사용의 주의점

1. stackoverflow

• 잘못 작성하면 stackoverflow가 발생하여 해당 프로그램이 먹통이된다.

2. 유지보수의 어려움

• 재귀를 사용하면 코드가 깔끔해지는 효과가 있지만, 협업을 하는 경우에 재귀로 작성을 한다면, 다른사람이 해당 코드를 알아보기 어렵고, 그에 따라 유지보수가 어려워진다.

3. 왠만하면 반복문으로

• 재귀로 짤 수 있는 것들은 대부분 반복문으로 작성이 가능하므로 알아보기 힘들것 같은 복잡한 코드는 반복문을 이용하여 작성하는것이 좋다.