2020.07.08 Javascript Basic [8. 재귀]

페어분과 같이 답을 작성하고 수정하면서 했지만 다시 한번 보면서 공부하기 위해 따로 저장하는 공간입니다.

 

이번에 리커전 과제를 시작하기 전에 풀어볼 수 있는 재귀 관련 문제가 코플릿 Basic에 업데이트가 되었습니다. 

9시에는 강의 듣고, 10시부터 페어와 Coplit Basic [8.재귀] 문제부터 풀어주시면 됩니다!

 

아 이렇게 또 문제를 풀기 시작했다. JS의 알고리즘을 만들때가 제일 어렵다는 그시간! 험난한 시간끝에 다 만들었지만;; 거의 도움을 많이 받았다. 이렇게 또 한번 통과를 했다. 10번 문제는 시간이 없어 혼자풀었지만 factorial 개념만 있다면 그 전것들보다 풀기 쉬웠던것 같다.

 

시작전

memoization에 대해 나중에 따로 적어놔야겠다.

 

01_factorial

 

factorial(num)은 자연수 1부터 n까지의 곱을 계산하는 함수입니다.

factorial(1) = 1

factorial(2) = 1 * 2 = 2

factorial(3) = 1 * 2 * 3 = 6

factorial(4) = 1 * 2 * 3 * 4 = 24 // ...

num이 주어졌을 때, factorial(num)을 계산하는 함수 factorial을 재귀함수의 형태로 완성하세요.

입력

인자 1 : num

number 타입의 num (num은 0 이상의 정수)

출력

number 타입의 자연수 (1 * 2 * ... * num)

예외

• factorial(0)은 1로 정의됩니다.
• 음수 입력은 들어오지 않습니다.

입출력 예시

let output = factorial(10); console.log(output); // --> 3628800

 

이건 강의를 듣고 기본적으로 factorial이라는 개념이 그 수학 부분 끝에 나왔던 기억이있는데... 10년도 더 된 기억인데 기억이나다니..;; ! <-

 

function factorial(num) {

if (num <= 1) {

return 1;

}

return num*factorial(num-1);

};

 

우선 for 문을 안쓰려고 무척 페어분과 고민을 해서 풀었던 시간이었던것 같다.

 

02_sumTo

 

sumTo(num)은 자연수 1부터 n까지의 합을 계산하는 함수입니다.

sumTo(1) = 1

sumTo(2) = 1 + 2 = 3

sumTo(3) = 1 + 2 + 3 = 6

sumTo(4) = 1 + 2 + 3 + 4 = 10 // ...

num이 주어졌을 때, sumTo(num)을 계산하는 함수 sumTo를 재귀함수의 형태로완성하세요.

입력

인자 1 : num

number 타입의 num (num은 0 이상의 정수)

출력

number 타입의 자연수 (1 + 2 + ... + num)

예외

• n * (n + 1) / 2 와 같은 공식의 사용은 금지됩니다.
• 음수 입력은 들어오지 않습니다.

입출력 예시

let output = sumTo(10); console.log(output); // --> 55

 

function sumTo(num) {

  if(num ===0){

   return 0;

 }

  return num +sumTo(num-1);

};

 

03_arrSum

 

array를 인자로 받아 array의 모든 요소의 합을 계산하는 함수 arrSum을 재귀함수의 형태로 완성하세요.

입력

인자 1 : arr

number 타입을 구성 요소로 갖는 array

출력

number 타입의 정수 arr[0] + arr[1] + ... + arr[n], n === arr.length

예외

• 입력으로 들어오는 arr의 모든 요소는 정수 값을 갖는다고 가정합니다.
• 빈 배열의 합은 0 입니다.

입출력 예시

let output = arrSum([-1, -2, 1, 3]); console.log(output); // --> 1

힌트

• array는 head와 tail을 통해 재귀적으로 정의될 수 있습니다.
• head는 array의 첫 요소를 말합니다.
• tail은 array이 head가 제거되고 남은 배열을 말합니다.

1. [ ] => [ ] 2. [1] => 1 + [ ] 3. [1, 2] => 1 + [2] 4. [1, 2, 3] => 1 + [2, 3]

• 3번의 [2]는 2번에 의해서 2 + [ ]로 정의되고, 따라서 [1, 2]는 최종적으로 1 + 2 + [ ] 로 정의될 수 있습니다.
• 같은 방식으로 4번을 정의해보세요.
• 길이가 1 이상인 array가 주어졌을 때 head와 tail은 각각 다음과 같이 구할 수 있습니다.const head = array[0]; const tail = array.slice(1);
• arrSum(arr)은 arr의 head에 arrSum(tail)을 더하는 방식으로 구할 수 있습니다.

여기서 부터 나는 시간의 방으로 들어가기 시작했다. [순삭의 시간]

 

function arrSum(arr) {

  if (arr.length < 1) {

  return 0;

 }

 

 const head = arr[0];

 const tail = arr.slice(1);

  return head +arrSum(tail);

};

 

04_arrProduct

문제

array를 인자로 받아 array의 모든 요소의 곱을 계산하는 함수 arrProduct을 재귀함수의 형태로 완성하세요.

입력

인자 1 : arr

number 타입을 구성 요소로 갖는 array

출력

number 타입의 정수 arr[0] * arr[1] * ... * arr[n], n === arr.length

예외

• 입력으로 들어오는 arr의 모든 요소는 정수 값을 갖는다고 가정합니다.
• 빈 배열의 곱은 1 입니다.

입출력 예시

let output = arrProduct([1, -2, 1, 3]);

console.log(output); // --> -6

 

function arrProduct(arr) {

  if(arr.length < 1){

  return 1;

 }

 const head = arr[0];

 const tail = arr.slice(1);

 return head * arrProduct(tail);

};

 

05_arrLength

 

문제

array를 인자로 받아 array의 길이을 계산하는 함수 arrLength을 재귀함수의 형태로 완성하세요.

입력

인자 1 : arr

임의의 요소를 갖는 array

출력

number 타입의 자연수 n (n === arr.length)

예외

• arr.length의 사용은 금지됩니다.
• arr.isEmpty()를 통해 배열이 비어있는 지 확인할 수 있습니다.
  • [ ].isEmpty() === true
  • [1, 2].isEmpty() === false
• 빈 배열의 길이는 0입니다.

입출력 예시

let output = arrLength([1, -2, 1, 3]);

console.log(output); // --> 4

 

function arrLength(arr) {

  if(arr.isEmpty() === true){

  return 0;

}

 const tail = arr.slice(1);

 return 1 + arrLength(tail);

};

 

06_drop

 

array와 num을 인자로 받아 array의 요소 num 개를 순차적으로 제거하는 함수 drop을 재귀함수의 형태로 완성하세요.

입력

인자 1 : num

number 타입의 num (num은 0 이상의 정수)

인자 2 : arr

임의의 요소를 갖는 array

출력

순차적으로 num 개의 요소가 제거된 array (arr.length >= 0)

예외

• num과 arr.length 중 최대값만큼 제거합니다.

입출력 예시

let output = drop(2, [1, -2, 1, 3]); console.log(output); // --> [1, 3] output = drop(5, [1, -2, 1, 3]); console.log(output); // --> [ ]

 

function drop(num, arr) {

  if(num > arr.length){

  return [];

}

  else if (num ===0){

  return arr;

}

  arr.shift()

  return drop(num-1,arr);

}

 

07_take

문제

array와 num을 인자로 받아 array의 요소 num 개를 순차적으로 저장하는 함수 take을 재귀함수의 형태로 완성하세요.

입력

인자 1 : num

number 타입의 num (num은 0 이상의 정수)

인자 2 : arr

임의의 요소를 갖는 array

출력

순차적으로 num 개의 요소로 구성된 array (arr.length >= 0)

예외

• 더 이상 제거할 수 없는 경우 빈 배열을 리턴합니다.

입출력 예시

let output = take(2, [1, -2, 1, 3]); console.log(output); // --> [1, -2] output = take(5, [1, -2, 1, 3]); console.log(output); // --> [1, -2, 1, 3]

 

function take(num, arr) {

if( num === 0 || arr.length === 0){

return [];

}

const head = arr[0];

const tail= arr.slice(1);

 

return [head].concat(take(num-1,tail));

};

 

08_and

 

문제

array를 인자로 받아 array의 모든 요소의 논리곱(and)을 계산하는 함수 and를 재귀함수의 형태로 완성하세요.

입력

인자 1 : arr

boolean 타입을 구성 요소로 갖는 array

출력

boolean 타입 true 또는 false arr[0] && arr[1] && ... && arr[n], n === arr.length

예외

• 빈 배열의 논리곱은 true 입니다.

입출력 예시

let output = and([true, true, true]); console.log(output); // --> true output = and([true, true, false]); console.log(output); // --> false

 

function and(arr) {

const head = arr[0];

const tail = arr.slice(1);

 

if(arr.length ===0){

return true;

}

else if (head === false){

return false;

}

return and(tail);

};

 

09_or

 

문제

array를 인자로 받아 array의 모든 요소의 논리곱(or)을 계산하는 함수 or를 재귀함수의 형태로 완성하세요.

입력

인자 1 : arr

boolean 타입을 구성 요소로 갖는 array

출력

boolean 타입 true 또는 false arr[0] || arr[1] || ... || arr[n], n === arr.length

예외

• 빈 배열의 논리곱은 false 입니다.

입출력 예시

let output = or([true, true, false]); console.log(output); // --> true output = or([false, false, false]); console.log(output); // --> false

 

function or(arr) {

 

const head = arr[0];

const tail = arr.slice(1);

 

if(arr.length ===0){

return false;

}

else if (head === true){

return true;

}

return or(tail);

};

 

10_fibonacci

문제

0과 1로 시작하는 피보나치 수열이 있습니다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1입니다. 그 다음 2번째 피보나치 수 부터는 바로 직전의 두 피보나치 수의 합으로 정의됩니다. 피보나치 수열은 아래와 같이 나열할 수 있습니다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...

num이 주어졌을 때, fibonacci(num)을 계산하는 함수 fibonacci를 재귀함수의 형태로완성하세요.

입력

인자 1 : num

number 타입의 num (num은 0 이상의 정수)

출력

number 타입의 정수 (num 번째 피보나치 수)

예외

• 피보나치 수열은 0번부터 시작합니다.

입출력 예시

let output = fibonacci(5); console.log(output); // --> 5 output = fibonacci(9); console.log(output); // --> 34

 

function fibonacci(num) {

if( num <2){

return num;

}

return fibonacci(num-1)+ fibonacci(num-2);

};