[코플릿]재귀(1~3번)

김밍·2023년 4월 11일
0

코드스테이츠

목록 보기
2/3
post-thumbnail

1번

문제 및 조건

수(num)을 입력받아 1부터 num까지의 합을 리턴해야 합니다.

  • 입력
    인자1 : num
    • number 타입의 정수(num >= 0)
  • 출력
    • number 타입을 리턴해야 합니다.
    • 1 + 2 + ... + num
  • 주의사항
    • 함수 sumTo는 재귀함수의 형태로 작성합니다.
    • 반복문(for, while)사용은 금지됩니다.
    • n * (n + 1) / 2와 같은 공식의 사용은 금지됩니다.
    • 음수 입력은 들아오지 않습니다.
  • 입출력예시
let output = sumTo(10);
console.log(output); // --> 55
야무지게 등차수열의 합 공식도 금지 시켜놓으셨음...

재귀적 사고 및 코드 작성

1. 재귀함수의 입력값과 출력값 정의하기

입력값 : number => 출력값 : number

  • sumTo(num) : number => number

2. 문제를 작게 뽀갠다.

ex) num = 5인 경우, 1~5까지의 합을 구해야한다.
(1 + 2 + 3 + 4 + 5) = (1 + 2 + 3 + 4) + 5 = sumTo(4) + 5
					= (1 + 2 + 3) + 4 + 5 = sumTo(3) + 4 + 5
                    = (1 + 2) + 3 + 4 + 5 = sumTo(2) + 3 + 4 + 5
                    = (1) + 2 + 3 + 4 + 5 = sumTo(1) + 2 + 3 + 4 + 5
                    = () + 1 + 2 + 3 + 4 + 5 = sumTo(0) + 1 + 2 + 3 + 4 + 5

3. 단순한 문제 해결하기

여기서 재귀의 기초(base case)는 sumTo(0) === 0이다.

  • sumTo(num) : number => number
  • sumTo(0) === 0 : 입력값이 0 인 경우 해결!

4. 복잡한 문제 해결하기

sumTo(5) === sumTo(4) + 5
sumTo(4) === sumTo(3) + 4
sumTo(3) === sumTo(2) + 3
sumTo(2) === sumTo(1) + 2
  • sumTo(num) : number => number
  • sumTo(0) === 0 : 입력값이 0 인 경우 해결!
  • sumTo(num) === sumTo(num - 1) + num : 입력값이 0이 아닌 경우 해결!

5. 코드 구현하기

function sumTo(num) {
  //base case
  if(num === 0) {
    return 0
  }
  //recursive case
  return sumTo(num - 1) + num;
}

2번

문제 및 조건

수를 입력받아 홀수인지 여부를 리턴해야 합니다.

  • 입력
    인자1 : num
    • number 타입의 정수
  • 출력
    • boolean 타입을 리턴해야 합니다.
  • 주의사항
    • 함수 isOdd는 재귀함수의 형태로 작성합니다.
    • 반목문(for, while) 사용은 금지됩니다.
    • 나눗셈(/), 나머지(%) 연산자 사용은 금지됩니다.
    • 0은 짝수로 간주합니다.
  • 입출력 예시
let output = isOdd(17);
console .log(output); // true
output = isOdd(-8);
console.log(output); // false

재귀적 사고 및 코드 작성

1. 재귀함수의 입력값과 출력값 정의하기

입력값 : number, 출력값 : boolean

  • isOdd(num) : number => boolean

2. 문제를 작게 뽀갠다

ex) num = 5인 경우, 2씩 빼주는 과정을 반복하여 나머지가 0인지 1인지를 찾는다.
5 - 2 = 3
	  = 3 - 2
      = 1

3. 단순한 문제 해결하기

여기서 재귀의 기초(base case)는 계속하여 2를 뺐을때 결과값이 0인지 1인지 판별하는것이다.
문제의 조건에서 0은 짝수로 간주합니다. 라고 했기때문에 1인 경우 true, 0인 경우 false이다.

  • isOdd(num) : number => boolean
  • num === 1 : 입력값이 1인 경우 true! 해결!

4. 복잡한 문제 해결하기

문제에서 정수타입이라고 하였기때문에 음수에 대한 복잡한 부분도 해결해주어야한다.
이런 경우 num < 0인 경우 isOdd(-num)을 하여 양수로 바꿔준다.
num의 절대값이 1보다 큰 경우 -2를 반복 작업하여 0 혹은 1의 결과값이 나올때까지 계속해준다.

  • isOdd(num) : number => boolean
  • num === 1 : 입력값이 1인 경우 true! 해결!
  • num < 0 이면 isOdd(-num)으로 양수로 만들어주기, num > 1 이면 isOdd(num - 2) : 그렇지 않은 경우 해결!

5. 코드 구현하기

function isOdd(num) {
  if(num === 0) {
    //base case
    //0은 짝수로 간주한다 하였으므로 false
    return false
  } else if (num === 1) {
    // 1은 홀수이기때문에 true
    return true
  }
  if(num < 0) {
    //recursive case
    //num이 음수인 경우 양수로 바꿔주기
    return isOdd(-num)
  }
  //num의 절대값이 1보다 큰 경우 -2를 반복해주기
  return isOdd(num - 2);
}

3번

문제 및 조건

수를 입력받아 n-factorial(n! : 엔-팩토리얼)의 값을 리턴해야 합니다.
n!은 1부터 n까지 1씩 증가한 모든 값의 곱입니다.

  • 입력
    인자1: num
    • number 타입의 정수(num >= 0)
  • 출력
    • number 타입을 리턴해야 합니다.
    • 1 2 ... * num
  • 주의사항
    • 함수 factorial은 재귀함수의 형태로 작성합니다.
    • 반복문(for, while) 사용은 금지됩니다.
    • factorial(0)은 1로 정의됩니다.
    • 음수 입력은 들어오지 않습니다.
  • 입출력 예시
let output = factorial(10);
console.log(output); // 3628800

재귀적 사고 및 코드 작성

1. 재귀함수의 입력값과 출력값 정의하기

입력값 : number, 출력값 : number

  • factorial(num) : number => number

2. 문제를 뽀개고 경우의 수 나누기

ex) num = 5인 경우,
5! = 4! + 5
   = 3! * 4 * 5
   = 2! * 3 * 4 * 5
   = 1! * 2 * 3 * 4 * 5
   = 0! * 1 * 2 * 3 * 4 * 5

3. 단순한 문제 해결하기

문제의 조건에서 factorial(0)은 1로 정의됩니다.에 따라 0! === 1이다. 이것이 재귀의 기초(base case)가 된다.

  • factorial(num) : number => number
  • factorial(0) === 1: num = 0인 경우: 문제 해결!

4. 복잡한 문제 해결하기

ex) num = 5인 경우,
5! = 4! + 5
   = 3! * 4 * 5
   = 2! * 3 * 4 * 5
   = 1! * 2 * 3 * 4 * 5
   = 0! * 1 * 2 * 3 * 4 * 5

여기서 num! = (num - 1)! * num인 것을 알 수 있다.
즉, factorial(num) = factorail(num - 1) * num이다.

  • factorial(num) : number => number
  • factorial(0) === 1: num = 0인 경우: 문제 해결!
  • factorial(num) = factorail(num - 1) * num : recursive case 해결!

5. 코드 구현하기

function factorial(num) {
  if(num <= 1) {
    //base case
    return 1;
  }
  //recursive case
  return factorial(num - 1) * num;
}

0개의 댓글