Javascript 재귀함수 배열 - javascript jaegwihamsu baeyeol

재귀(recursion) 함수는 자기 자신을 호출하는 함수를 말합니다.

for문과 같은 반복문은 재귀로 변환할 수 있으며, 재귀로 코드를 작성하는 방법이 더 효율적일 수도 있습니다.

이번 포스팅에서는 반복문을 재귀 함수로 변경하는 코드를 기반으로 재귀에 대한 내용을 정리합니다.

재귀에 대한 개념 및 이론적인 설명은 하지 않으며, 함수형 프로그래밍과 연관 지어 설명합니다.

배열의 합계를 재귀 함수로 작성

반복문을 사용하여 5부터 0까지의 합계를 반환하는 코드입니다.

var totalValue = function(param) {
  var sum = 0;
  for(var loop = param; loop > 0; loop--) {
    sum += loop;
  }
  return sum;
}

console.log(totalValue(5));
// 15

반복문을 재귀 함수로 작성한 코드입니다.

보기 좋은 코드는 아니지만, 코드가 좀 더 심플해졌습니다.

var recurFunc = function(param) {
  return (param > 0) ? (param + recurFunc(param - 1)) : param;
}

console.log(recurFunc(5));
// 15

이렇게 반복문을 재귀 함수로 변환하여 코드를 좀 더 심플하게 작성할 수 있습니다.

비동기 프로세스에서 재귀 함수를 사용

아래와 같은 경우는 재귀 함수를 사용하는 것이 좋습니다.

api 요청을 하는 코드를 작성한다고 가정합니다.

만약, api 요청을 실패하면 다시 요청을 합니다.

최대 5번 재요청을 합니다.

아래 코드는 크롬 Console에서 실행 가능합니다.

// 요청 횟수
var requestMaxCount = 5;

// url
var urlString = "https://jsonplaceholder.typicode.com/posts/1";

var apiReqest = function(url, count) {
  console.log(`*****${count}번째 요청중*****`);
  if(count > 0) {
    fetch(url)
      .then(function(response) {
        console.log(response);
        // 응답은 받았으나 404 error와 같은 에러일 경우 재요청
        if(response.ok === false) {
          apiReqest(url, count - 1);
        }
      })
      // 에러 발생시 재요청
      .catch(function(error) {
        console.log("error:", error);
        apiReqest(url, count - 1);
      });
  }
}

console.log(apiReqest(urlString, 5));

만약, url이 잘못되었거나 네트워크 에러가 발생할 경우 재요청을 하게 됩니다.

0번째 요청인 경우 if문 조건에 의해 api 요청을 수행하지 않습니다.

아래는 reponse는 받았으나 404에러인 경우입니다.

데이터 구조를 검색

재귀 함수는 중첩된 객체의 프로퍼티 값을 추출 또는 접근하는 용도로 사용할 수 있습니다.

다음 코드는 중첩된 객체에서 next 프로퍼티의 값을 배열로 반환하는 재귀 함수입니다.

let list = { 
  value: 1,
  next: { 
    value: 2, 
    next: { 
      value: 3, 
      next: { 
        value: 4, 
        next: null 
      } 
    } 
  } 
};

function printList({ value, next }) {
    return [value, ...(next ? printList(next) : [])]
}

console.log(printList(list));

단점도 존재하는 재귀

이러한 재귀 함수는 코드를 간결해주고 비동기 프로세스에서 유용해 보이지만, 단점도 존재합니다.

재귀 함수의 호출 횟수가 많아질수록 재귀의 깊이가 깊어집니다.

자바스크립트 엔진은 재귀의 깊이가 깊은 경우 정상적으로 최적화 불가능하며, 오류가 발생합니다.

이러한 경우 트램폴린(trampoline)과 스트림(stream) 같은 기법을 사용하여 재귀를 수동으로 최적화할 수 있습니다.

자바스크립트 엔진에서 스택의 제한을 없애고자 하는 계획이 있기 때문에 트램폴린과 스트림은 정리하지 않았습니다.

마무리

이번 포스팅에서는 재귀에 대해 정리하였습니다.

정리하자면, 다음과 같습니다.

• 반복문은 재귀 함수로 변환할 수 있다.
• 반복문보다는 재귀가 더 유용하다.
• 단, 재귀의 깊이가 길어질수록 스택의 제한으로 오류가 발생할 가능성이 높다.

트램폴린과 스트림에 대해 정리를 하고자 했으나 자료가 별로 없고 심플한 내용은 아니라서 작성하지 않았습니다.

트램폴린에 대해 궁금하신 분들은 아래 링크에서 설명하고 있으니 참고하시면 되겠습니다.

https://medium.com/@jooyunghan/js-%EC%A0%9C%EB%84%88%EB%A0%88%EC%9D%B4%ED%84%B0%EB%A1%9C-%EC%8A%A4%ED%83%9D%EC%98%A4%EB%B2%84%ED%94%8C%EB%A1%9C-%ED%94%BC%ED%95%98%EA%B8%B0-a070ebbe5dc7

JS 제너레이터로 스택오버플로 피하기

“모나딕 파서”글에서 만든 파서 같은 형태를 Recursive Descent Parser 라고 한다. 재귀적 문법 구조를 처리하는 파서를 직접 만든다고 했을 때 제일 구현하기 쉬운 방법 중 하나다. 문법에 따라 거의

medium.com

패스트캠퍼스 코딩테스트 강좌의 잔재미코딩 님 부분을 참고하였습니다.

재귀함수

recursive call

함수 안에서 동일한 함수를 호출하는 형태

팩토리얼 구현

1! = 1
2! = 1 * 2
3! = 1 * 2 * 3
4! = 1 * 2 * 3 * 4
n! = n * (n-1)!

const factorial = n => {
  if (n > 1) {
    return n * factorial(n - 1);
  } else {
    return n;
  }
};

console.log(factorial(1)); // 1 
console.log(factorial(2)); // 2
console.log(factorial(3)); // 6
console.log(factorial(4)); // 24
console.log(factorial(5)); // 120

시간복잡도

n의 2제곱

재귀 호출의 일반적인 형태

// 1)
const func = 입력값 => {
  if (입력값 > 일정값) { // 입력이 일정값 이상이면
    return func(입력값 - 1) // 입력보다 작은 값
  } else {
    return 일정값, 입력값, 다른 특정값 // 재귀호출 종료
  }
}

// 2)
const func = 입력값 => {
  if (입력값 <= 일정값) { // 입력이 일정값보다 작거나 같으면
    return 일정값, 입력값, 다른 특정값 // 재귀호출 종료
  }
  return func(입력보다 작은 값);
}

2번째 형식으로 팩토리얼 예제를 다시 구현해보면

const factorial = n => {
  if (n <= 1) {
    return n;
  }
  return n * factorial(n - 1);
};

console.log(factorial(1)); // 1 
console.log(factorial(2)); // 2
console.log(factorial(3)); // 6
console.log(factorial(4)); // 24
console.log(factorial(5)); // 120

재귀호출은 스택의 전형적인 예다

재귀호출 예시

예제 1) 1부터 n까지의 곱이 출력되게 하라.

const multiple1 = n => {
  if (n <= 1) {
    return n;
  }
  return n * multiple1(n - 1);
};
console.log(multiple1(10)); // 3628800

예제 2) 숫자가 들어있는 배열이 주어졌을 때, 배열 요소들의 합을 구하여라

const sum = array => {
  if (array.length <= 1) {
    return array[0];
  }
  const first = array.shift();
  return first + sum([...array]);
};

const array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
console.log(sum(array)); // 55

spread 문법 복습

예제 3) 회문 palindrome을 판별할 수 있는 함수를 만들어라. (eye, madam, level 처럼 거꾸로 읽어도 제대로 읽혀지는 것)

const palindrome = str => {
  // 해당 문자열의 길이가 1이거나 0이면(처음부터 0, 1이거나 회문 검사를 끝까지 통과했거나)
  if (str.length <= 1) {
    return true;
  }
  // 배열(문자열)의 길이 -1 이면 마지막 인덱스
  const lastIndex = str.length - 1;

  // 첫 글자와 마지막 글자가 같으면
  if (str[0] === str[lastIndex]) {
    // (동일한) 첫 글자와 마지막 글자를 제외한 글자를 다시 회문 검사
    return palindrome(str.slice(1, lastIndex));
  } else {
    // 검사 도중 첫 글자와 마지막 글자가 같지 않으면 false
    return false;
  }
};

console.log(palindrome("madam"));

예제 4) 정수 n에 대해 n이 홀수면 3 * n + 1을 하고 n이 짝수면 n을 2로 나눈다. 이를 n이 결국 1이 될 때까지 반복한다. n을 입력받아 n이 1이 되는 과정을 모두 출력하는 함수를 작성하세요.

const oneMaker = n => {
  console.log(n);
  if (n === 1) {
    return n;
  }
  if (n % 2 !== 0) {
    // 홀수
    // parseInt(정수로변환할대상, n진법)
    return oneMaker(parseInt(3 * n + 1, 10));
  } else {
    // 짝수
    return oneMaker(parseInt(n / 2), 10);
  }
};

oneMaker(3);

예제 5) 정수 n이 입력으로 주어졌을 때, n을 1, 2, 3의 합으로 나타낼 수 있는 방법의 수를 구하시오

예)

정수 4를 1, 2, 3의 조합으로 나타내는 방법은 다음과 같이 총 7가지가 있음
1+1+1+1
1+1+2
1+2+1
2+1+1
2+2
1+3
3+1

const func = n => {
  // 규칙성이 발견되지 않는 경우들.
  if (n === 1) {
    return 1;
  } else if (n === 2) {
    return 2;
  } else if (n === 3) {
    return 4;
  }

  // 규칙성 시작
  return func(n - 1) + func(n - 2) + func(n - 3);
};

console.log(func(6));

예제 6) 피보나치 수열

0번째 항은 0, 1번째 항은 1, 그다음부터는 전전번 항과 전번 항을 합.

const fibo = n => {
  if (n <= 1) {
    return n;
  } else {
    return fibo(n - 1) + fibo(n - 2);
  }
};