[Algorithm] Recursion

😐 재귀(Recursion)

재귀란, 자신을 정의할 때 자신을 참조하는 것을 의미한다.

• 재귀 함수: 재귀 개념을 사용한 재귀함수는 종료 조건에 충족할 때까지 자기 자신을 호출하는 함수이다. 재귀 함수가 실행되면 stack 자료구조에 함수의 기본 정보가 저장된다. 기본 정보가 저장되는 공간을 stack frame이라고 하며 해당 위치에는 함수의 기본 정보인 매개변수, 지역변수, 복귀주소 등이 저장된다.

function recursive(인자) {
  작업수행
  if (조건충족) {
    return 결과;
  } else {
    return recursive(작업된인자);
  };

//값이 n인 숫자를 입력받아 1 ~ n까지 출력하는 함수를 작성하여라.
//재귀와 스택을 사용하여 구현할 수 있다.

let num = 3;
function DFS(L) {
  if (L === 0) return;
  else {
    //stack 자료구조의 FILO 특성으로 인해 console.log는 바로 실행되지 않는다.
    //stack에 쌓인 작업이 들어온 순서 반대로 실행되며 1 2 3이 순서대로 출력된다.
    DFS(L-1);
    console.log(L); //----- 복귀 주소
  }
}

DFS(num); // 1 2 3

재귀함수로 작성될 수 있는 코드는 for문이나 반복문으로도 작성이 가능하다. 하지만 어떤 경우에 한에서는 재귀함수로 작성하는 것이 더 효율적일 수 있다.

• 예를 들면 어떤 Array에 담긴 숫자들의 총 합을 구해야 한다고 하자! Array 안의 숫자가 전부 숫자 형태라면 문제가 없지만 중간 중간 참조형 데이터가 삽입되어 있다면 그 데이터의 깊이만큼 for문을 추가해야하는 단점이 생긴다. 그런 경우에는 재귀를 이용하면 쉽게 해결할 수 있다.

  

• 하지만 재귀함수에도 단점이 없는 것은 아니다. 재귀함수는 호출될 때마다 메모리의 스택에 쌓인다. 한계치 이상으로 호출되서 스택이 넘치면 메모리 부족으로 에러가 발생할 수 있다. 이런 문제때문에 많은 언어들이 Tali Call Optimization이라는 기능을 제공한다.(JavaScript는 ES6부터 해당 기능을 제공한다.)

  

출처: YOUTUBE-얄팍한 코딩사전