9주차 배운 내용

재귀함수에 대해 배웠습니다.

1. 하향식, 상향식 접근법

하향식 분석(top to bottom)

출력형태를 만들어 놓고 회수하는 형태이다. 결과가 이전의 결과에 영향을 받는 것는 형태로 의존성이 있다고 본다.

상향식 분석(bottom to top)

가장 아래쪽부터 위로 쌓아 올리면서 분석하는 방법으로 하향식 분석과 분석 방식이 정반대이다.

2. 재귀함수

기저조건을 포함하여 자기자신을 호출하는 함수이다.

• 장점
  - 외부 변수 사용을 줄일 수 있다.
  - 변수 사용이 줄어든다는 뜻은 프로그램에 오류가 생길 가능성이 줄어들고, 프로그램이 정상적으로 돌아가는지에 대한 증명이 쉬워진다 .
  - 재귀적인 함수사용(하향식 접근)이 어울리는 방식에는 재귀함수를 사용하는게 좋다.
• 단점
  - 반복문보다 메모리 사용량이 많고 수행기간이 길어질 수 있다.
  - 기저조건이 불완전하면 무한반복으로 에러가 발생한다.

사용예시

• JSON(parser)가 오브젝트를 순회할 때 재귀를 사용한다.
• 웹에서 DOM등을 순회할 때도 사용한다. ex)DOM API querySelector
• 알고리즘과 코딩테스트 등에도 사용한다.
• 디자인 패턴의 컴포지트 패턴 -> 트리구조 만들 때 쓴다.

코드예시

function recursiveSum(num) { 
  //기저조건(base case)
  if (num === 0) return num;
  return num + recursiveSum(num - 1);
}

/*
 * num - 1 을 파라미터로 같은 함수를 반복해서 호출하고 기저조건에 성립 시 
 * 파라미터로 받은 값을 호출의 역순으로 반환한다
 */
------------------------------------------------------------<스택 0 init>
recursiveSum(5)

------------------------------------------------------------<스택 1>
return 5 + recursiveSum(4)

------------------------------------------------------------<스택 2>
return 5 + recursiveSum(4) -> return 4 + recursiveSum(3) 

------------------------------------------------------------<스택 3>
return 5 + recursiveSum(4) -> return 4 + recursiveSum(3) 
  -> return 3 + recursiveSum(2) 

------------------------------------------------------------<스택 4>
return 5 + recursiveSum(4) -> return 4 + recursiveSum(3) 
  -> return 3 + recursiveSum(2) -> return 2 + recursiveSum(1)

------------------------------------------------------------<스택 5>
return 5 + recursiveSum(4) -> return 4 + recursiveSum(3) 
  -> return 3 + recursiveSum(2) -> return 2 + recursiveSum(1) 
    -> return 1 + recursiveSum(0) <=> if (0 === 0) return 0

------------------------------------------------------------<스택 5>
return 5 + recursiveSum(4) -> return 4 + recursiveSum(3) 
  -> return 3 + recursiveSum(2) -> return 2 + recursiveSum(1) 
    -> return 1 + 0 <=> 1

------------------------------------------------------------<스택 4>
return 5 + recursiveSum(4) -> return 4 + recursiveSum(3) 
  -> return 3 + recursiveSum(2) -> return 2 + 1 <=> 3

------------------------------------------------------------<스택 3>
return 5 + recursiveSum(4) -> return 4 + recursiveSum(3) 
  -> return 3 + 3 <=> 6

------------------------------------------------------------<스택 2>
return 5 + recursiveSum(4) -> return 4 + 6 <=> 10

------------------------------------------------------------<스택 1>
return 5 + 10 <=> 15

------------------------------------------------------------<스택 0 init>
return 15

//팩토리얼 예시
function recusiveFactorial(num) {
  //기저조건(base case)
  if (num === 1) return num; //0! = 1
  return num * recusiveFactorial(num - 1);
}

recusiveFactorial(5); // 120

재귀함수의 한계점

• 스택 한계치 이상으로 호출되어 생기는 Maximum number of stacks exceeded에러
• 반복문에 비해 시간이 오래 걸림
• 함수호출과 복귀를 위한 context switching 비용이 발생하기 때문에, 속도가 상대적으로 느립니다. -> 오버헤드가 발생하여 속도가 느려집니다.

꼬리 재귀

재귀 호출이 끝난 후 현재 함수에서 추가 연산을 요구하지 않도록 구현하는 재귀의 형태입니다. 이를 이용하면 함수 호출이 반복되어 스택이 깊어지는 문제를 컴파일러가 선형으로 처리하도록 알고리즘을 바꿔 스택을 재사용할 수 있게 됩니다. 다시말해 재귀함수의 한계점을 해결하기 위한 방법입니다.

상향식으로 쌓아올리면서 연산결과를 같이 전달한다.
컴파일러가 반복문으로 바꿔줍니다.

코드예시

function factorial(n, total = 1) {
  if (n === 1) return total
  return sum(n - 1, n * total)
}

factorial(4)