재귀함수(feat.순열)

재귀함수

• 자신을 정의할 때 자기 자신을 재참조하는 함수 

function fibonacci(n){
//재귀의 가장 중요한 첫번째는 무한루프에 빠지지 않게 탈출로를 만드는 것이다
//이것을 BASE CASE라고 한다
//fibonacci 함수에서 BASE CASE는 
//n이 2보다 작아질 경우 n값을 리턴하는 것이다
  if(n < 2){
    return n
  }
  
 //문제를 더 쪼갤 수 있는 경우는 RECURSIVE CASE라고 한다
 
  return fibonacci(n-1) + fibonacci(n-2)
}

fibonacci(6) //8
fibonacci(5) //5

//fibonacci 수열은 0 1 1 2 3 5 8 13...

fibonacci(4)를 입력받는 경우 3을 리턴하는데 이 때 재귀함수가 발동하는 경로는 이렇다 

fibonacci(4 - 1)  => fibonacci(3 - 1)  => fibonacci(2 - 1) 이때 BASE CASE가 동작하고

fibonacci(1)은 BASE CASE에 의해 1값을 리턴하게 된다. 이 리턴값을 가지고 다시 위로 올라가기 시작한다!

fibonacci(2) = fibonacci(1) + fibonacci(0)이기 때문에 fibonacci(2) = 1 값을 가지게 되고 다시 올라가서

fibonacci(3) = fibonacci(2) + fibonacci(1)이기 때문에 fibonacci(3) = 2 값을 가지게 된다. 마지막으로

fibonacci(4) = fibonacci(3) + fibonacci(2)고 fibonacci(4) = 3 값을 반환하게 된다

 

순열

• 순서대로 뽑아서 줄을 세우는 것이다!

function test(arr){
  let result = [];
  
  //BASE CASE 배열의 길이가 1이 되면 멈춘다 
  if(arr.length === 1){
    result.push(arr)
  }else{
    for(let i = 0; i < arr.length; i++){
    //처음 숫자를 고정한다  
      let fixed = arr[i]
    //고정된 숫자를 제외한 나머지를 배열로 만든다
      let rest = [...arr.slice(0, i), ...arr.slice(i + 1)]
    //재귀로 다이브 위의 과정을 고정된 숫자를 제외한 배열을 가지고 다시 한 번 돌린다 
    //배열의 길이가 1이 되면 멈추고 그 값을 가지고 온다
      let perm = test(rest)
  	//고정된 숫자와 perm의 요소를 합친다 perm은 이중배열로 요소가 배열이다 
      let conc = perm.map(el => [fixed, ...el])
      result.push(...conc)
    }
  }
  return result
}

test([1,2,3]) 
//[
//  [ 1, 2, 3 ],
//  [ 1, 3, 2 ],
//  [ 2, 1, 3 ],
//  [ 2, 3, 1 ],
//  [ 3, 1, 2 ],
//  [ 3, 2, 1 ]
//]