Algorithm] Recursion

😐 재귀(Recursion)

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

• 재귀 함수: 재귀 개념을 사용한 재귀함수는 종료 조건에 충족할 때까지 자기 자신을 호출하는 함수이다.

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

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

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

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

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