재귀란?
재귀는 함수에서 자기 자신을 다시 호출해 작업을 수행하는 알고리즘입니다!
종료 조건이 충족될 때까지 반복적으로 스스로를 불러내면서 주어진 작업을 수행합니다!
재귀를 예를 들어...
팩토리얼을 계산하는 함수를 작성해 보겠습니다 :)
이렇게 3!을 구하려면...3은 1이 아니니까 3 x fac(2)가 됩니다!
그리고 2는 1이 아니니까 2 x fac(1)이 됩니다!
1은 1이니 1이 리턴됩니다!
그래서 총..3 x 2 x 1 = 6이 리턴됩니다 😎
이걸 그림으로 표현하자면..!
이렇게 어떤 함수 안에서 자기 자신을 호출하는 것을 재귀라고 합니당 😊
재귀는 언제 사용하는 게 좋을까?!
재귀는 이러한 상황에서 사용하시면 매우 좋습니다!
- 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우
- 중첩된 반복문이 많거나 반복문의 중첩 횟수를 예측하기 어려운 경우
모든 재귀 함수는 반복문으로 표현할 수 있습니다! 반복문을 사용하는 것이 더 쉬운 경우도 있습니다..! 하지만 재귀를 사용하는 것이 더 쉬울 때도 많습니다!
예를 들자면..
let num = [3, 4, 5, [1, 2, 4], 5, 6]이런 식으로 배열이 섞여 있는 경우에는 재귀를 적용하는 게 더 쉽습니다 ㅎㅎ (하노이의 탑을 재귀 함수로 작성한 경우와 그렇지 않은 경우로 비교해 보세요!)
코플릿
sumTo : 수(num)를 입력받아 1부터 num까지의 합을 리턴해야 합니다
입출력 예시
let output = sumTo(10);
console.log(output); // --> 55내가 작성한 코드는
function sumTo(num) {
if (num === 0){
return 0
}
if (num === 1) {
return 1
}
return num + sumTo (num - 1)
}앞에 팩토리얼을 배워서 쉽게 풀었다 ! ㅎㅎㅎ
isOdd : 수를 입력받아 홀수인지 여부를 리턴해야 합니다
입출력 예시
let output = isOdd(17);
console.log(output); // --> true
output = isOdd(-8);
console.log(output); // --> false내가 작성한 코드는
function isOdd(num) {
if (num === 0) {
return false
}
if (num === 1) {
return true
}
if (num < 0 ) {
return isOdd (num +2)
}
if (num > 0 ) {
return isOdd (num -2)
}
}여기서부터 막혔담...나눗셈(/)과 나머지(%) 연산자 사용이 금지라길래..그대로 머리가 멈췄다! 그래서 몇 분 고민하다가..결국..레퍼런스 코드를 앞부분만 살짝 봤다...ㅜㅜ num이 0일ㄷ 때와 1일 때 나눈 거 보고..힌트를 얻어서 풀 수 있었다..두 번째 문제부터 머리 터졌다 ㅜ
fibonacci : 수(num)를 입력받아 피보나치 수열의 num번째 요소를 리턴해야 합니다
입출력 예시
let output = fibonacci(9);
console.log(output); // --> 34내가 작성한 코드는
function fibonacci(num) {
if (num <= 1) {
return num
}
return fibonacci(num - 1) + fibonacci(num - 2)
}피보나치가 (n-1) + (n-2) 라서..그나마 쉽게 작성할 수 있었다! 레퍼런스 코드 보니까 내 코드랑 똑같아서...뭔가 감동 ㅎ 전 문제를 통해 0이랑 1일 때 한 번에 묶으면 더 간결한 걸 깨달음..
arrSum : 배열을 입력받아 모든 요소의 합을 리턴해야 합니다
입출력 예시
let output = arrSum([-1, -2, 1, 3]);
console.log(output); // --> 1내가 작성한 코드
function arrSum(arr) {
if (arr.length === 0){
return 0
}
let head = arr[0]
const tail = arr.slice(1)
return head + arrSum(tail)
}빈 배열의 합은 0 이라서..조건문을 해줬다! 그리고 막혔다..힌트 보고 대충 눈치껏 때려 적음..ㅠㅠ 힌트 없었더라면.. 못 풀었을 거 같다
let head = arr[0]
const tail = arr.slice(1)
여기까지 힌트로 적고.. head 더할 테고 재귀니 arrSum 쓰고..tail 선언했으니..사용하고...그렇게 이해는 못 한 상태로 야매로 적었다 ㅜㅜ
drop : 수(num)와 배열을 입력받아 차례대로 num개의 요소가 제거된 새로운 배열을 리턴해야 합니다
입출력 예시
let output = drop(2, [1, -2, 1, 3]);
console.log(output); // --> [1, 3]
내가 작성한 코드
Retrospect 🧐
코플릿 어렵다! 알고리즘 기초 배워야겠다! 배열도 복습해야겠다 ㅎㅎ..
