재귀함수(recursive function)

1)정의

자신이 수행할 작업을 유사한 형태의 여러 조각으로 쪼갠 뒤 그 중 한 조각을 수행하고 나머지를 자기 자신을 호출해 실행하는 함수

2)for문 ->재귀문

-반복문

function sum(n){
 let ret =0;
 for(let i =1;i<=n;i++){
 ret +=i;
}
 return ret;
}

-재귀함수

function recursiveSum(n){   
   if(n===1){
return 1;
   }

return n+ recursiveSum(n-1);
}

3)재귀의 이점

-알고리즘 자체가 재귀적으로 표현하기 자연스러울 때, 가독성이 좋다.
-변수 사용을 줄여준다.

-재귀 호출은 코딩을 훨씬 간편하게 해 줄수 있는 무기가 된다.
예를들어 n개의 원소 중 네 개를 고르는 모든 경우를 출력하는 코드를 작성한다고 하자.
n=7일때 (0,1,2,3) (0,1,2,4),(0,1,2,5) e등등 모든 경우를 출력한다. 이 때 우리는 4중 for문으로 써서 이것을 간단하게 할수 있다.

for(int i =0;i<n;i++)
 for(int j =0;j<n;j++)
  for(int k =0;k<n;k++)
   for(int l =0;l<n;l++)
 cout <<i << " " << j << " " << k << " " << l << endl; 

만약 5개를 골라야하는 상황이 오면 5중 for문으로 쓰면된다. 골라야하는 것이 더 많아진다면 for문을 계속 추가해나가야 한다.
매우 비효율적이다. 하지만 재귀호출은 이런 경우에 단순한 반복문 보다 간결하고 유연한 코드로 작성할 수 있게 된다.

function pick(let n,let picked,let topick){
 if(topick ===0){ printPicked(picked); return ;}
  int smallest = picked.empty() ? 0: picked[picked.length-1] -1;
 for( int next = smallest; next <n; next ++){
  picked.push(next);
  pick(n,picked,toPick-1);
  picked,pop();
 }
}

과 같이 단순하게 코드를 작성할 수 있다.

4)문제를 쪼개어 생각하는 방법

1.기존의 문제에서 출발하여 더 작은 경우를 생각한다.
2같은 방식으로 문제가 더는 작아지지 않을 때까지 더 작은 경우를 생각한다.
3.문제가 간단해져서 바로 풀수 있게 되는 순간 앞서 생성한 문제를 차근차근 해결한다.
이 과정에서 자기자신을 호출한다

5) 재귀 함수와 메모리 사용량 간의 관계 (javascript recursion memory leak)

실행컨텍스트는 메모리를 차지하기 때문에, 재귀 함수 사용시 메모리 요구사항에 유의해야한다.
깊이(depth)를 늘리면 깊이가 줄어들 때마다 depth 만큼의 실행 컨텍스트가 저장될 메모리 공간 필요 → 반복문 기반 알고리즘을 통해 메모리 사용((=함수 호출의 비용) 절약 가능