[알고리즘 - Algorithm] 재귀함수 (Recursion Function)

오늘은 재귀함수에 대하여 알아보겠다.
비전공자로 개발을 시작해서 경력을 쌓는 동안에 알고리즘 공부를 하지 않았다. 정말 안일한 했고 허송세월을 보낸 것 같다. 난 지난 2년간 무얼했는가.. 어차피 지나간 시간! 후회할 시간에 지금부터라도 알아보자! 😀

재귀함수 ?

개념

재귀함수란 컴퓨터 과학에 있어 재귀(Recursion)는 자신을 정의할 때 자기 자신을 재참조하는 방법을 뜻하며, 이를 프로그래밍에 적용한 재귀 호출(Recursive call)의 형태로 많이 사용된다.
위키백과 참조

/// acc = accumulator 누산기(계산되며 누적되는 값)
/// arr = 배열
const recursive = (acc, arr) => {
  if (arr.length === 0) {
    return acc;
  } else {
    return recursive(acc + arr[0], arr.slice(1));
  }
};
recursive(0, [3,1,2,5,4])

위와 같은 함수를 재귀함수라고 한다. 특정 조건이 충족될 때 까지 자기 자신을 계속 호출하는 것이다. 결국 계속해서 반복하는건데 왜 for문이나 while문을 사용하지 않는 걸까 ??

여러 단계를 포함하는 배열일 경우

예를들어 다음과 같은 배열이 존재한다.
arr = [1,2,3,[4,3,[33,1,3,4],5],6,7,8,[6,3],2,1] 이 배열의안의 모든 숫자의 합을 구하고자 할 때 for를 사용해서는

for (let i=0; i<arr.length; i++) {
	if (typeof arr[i] !== 'number') {
      for (let a=0; a<arr[i].length; a++) {
        ....
      }
}

이러한 형식의 for문이 계속 반복될 것이고 배열속의 배열의 깊이단계를 특정하지 못할 경우에는 구현하기 힘들 것이다. 그래서 이러한 경우에는 재귀함수를 사용하면 매우 효율적으로 해결 가능하다!

let arr = [1,2,3,[4,3,[33,1,3,4],5],6,7,8,[6,3],2,1]

const recursive = (acc, arr) => {
	if (arr.length === 0) {
    	return acc 
    } else {
    return recursive(acc + 
      (typeof arr[0] === "number" ? arr[0] : recursive(0, arr[0])),
      arr.slice(1)
    );
  }
};

느낀점
재귀함수를 왜 쓰는가에 대한 의구심도 있었고 어렵게 다가왔었는데, 예제를 접하며 해보니깐 이해도 쉬웠고 활용도가 높을것 같다. 이제 DFS 알고리즘을 이해하는데 한걸음 다가갈 수 있다! 아자🤛🤛