재귀 함수

재귀 함수 : 

함수가 실행될 때 자기 자신을 호출하는 함수

함수의 선언이 끝나기 전에 자신을 다시 호출하는 함수

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

함수 안에서 본인을 호출

 

function answerByStory (question) {
  // 임의의 이야기에서 답 찾기
  let answer = findFromRandomStory();
  
  // 이야기 속에서 답이 나오지 않으면
  if (answer === null) {
    return answerByStory(question); // 재귀 호출
    
  // 답이 나오면
  } else {
    return answer; // 답을 반환
  }
}

 

비슷한 것으로 arguments.callee 가 있음

function factorial(n) {
  if (n === 0) {
    return 0;
  } else {
 // return factorial(n - 1)
    return arguments.callee(n - 1)
  }
}

---

재귀함수로 짜여진 코드는 for문이나 while문으로도 가능함

예 ) 단순히 숫자만 들어있는 배열의 총합을 구하는 것

let array1 = [1,4,5,2,8,3];

재귀함수는 jump가 잦아서 반복문에 비해 시간을 더 소모함

 

 

재귀함수를 써야할 때

여러 단계를 포함하는 데이터, 각종 정렬 알고리즘

예 ) 배열 안에 또 배열이 들어있고, 몇 단계로 내려가는지 알 수 없을 때

let array2 = [3,1,5,[3,7],23,[4,[8,9]]];

하노이의 탑 게임에 사용

 

 

재귀함수는 호출될 때마다 메모리의 스택에 쌓이게 됨

> 한계 치 이상으로 스택이 쌓이면 메모리 부족으로 에러 발생!

 

함수안에 함수가 함수를 부르고 그 함수가 또 함수를 부르기를 반복하기 때문에 결과는 무한히 반복

> 이와 같은 반복을 피하기 위해 장치를 넣어야함

// 무한 반복
function A(n) {
  console.log(n);
  A(n-1);
}

// 조건을 충족하면 return으로 종료
function A(n) {
  if (n < 0) {
  return;
  }
  console.log(n);
  A(n-1);
}

 

 

 

꼬리 재귀 최적화(Tail Call Optimization)

그래서 많은 언어들에서 꼬리 재귀 최적화를 제공함!

 

재귀함수를 컴퓨터가 재해석해서 선형 알고리즘으로 만들어 실행함

> 아무리 반복이 많이 일어나도 스택이 넘치는 일은 일어나지 않음

 

재귀함수를 사용하고 싶다면 사용하는 언어가 꼬리 재귀 최적화를 지원하는지 확인하면 좋음

 

꼬리 재귀를 하려면 함수 자체만 return해야 가능함

// 함수 자체만 return -> 꼬리 재귀 가능
function canTailRecurse (arg) {
  // ...
  return canTailRecurse (arg)
}



// 다른 것들이 섞여서 return -> 꼬리 재귀 불가능
function canNotTailRecurse (arg) {
  let n;
  // ...
  return n * canNotTailRecurse (arg)
}