배열 안에 원하는 값을 찾기 위해서 사용하는 방법이 두가지가 있는데 하나는 반복문을 사용하는것과 나머지 하나는 재귀를 사용하는 것이다.

재귀란?
함수가 자기 자신을 호출하는 것.

재귀를 쓴다고 해서 성능이 더 나아지는건 아니다. 재귀를 사용하면 프로그래머의 능력을 향상시킬수 있고, 반복문을 사용하면 프로그램의 성능을 향상시킬수 있다. 상황에 따라 적절한 방법을 사용하는 것이 좋다.

기본 단계와 재귀 단계

재귀 함수는 자기 자신을 호출하기 때문에 무한 반복하는 함수를 만들수 있다. 예를 들면 3..2..1 과 같이 카운트 다운 하는 함수를 만든다고 하자

function countDown(i){
  console.log(i)
  countDown(i - 1)
}
countDown(3)

위와 같은 코드를 실행 할때 무한 반복 하는 문제가 생긴다.

재귀 함수를 사용할때는 재귀를 언제 멈출지 알려줘야 한다. 그래서 모든 재귀 함수는 기본단계(basic case)와 재귀단계(recursive case)두 부분으로 나누어져있다.

재귀단계 : 함수가 자기 자신을 호출하는 부분
기본단계 : 함수가 자기 자신을 다시 호출하지 않는 경우, 즉 무한 반복을 막게 하는 부분

function countDown(i) {
  console.log(i);
  if (i <= 1) {
    return; // 기본 단계
  } else {
    countDown(i - 1); // 재귀 단계
  }
}

countDown(3);

스택

스택이란?
아주 단순한 자료구조이다.

호출 스택

호출 스택이란 여러개의 함수를 호출하면서 함수에 사용되는 변수를 저장하는 스택

function greet(name) {
  console.log(`hello, ${name} !`);

  greet2(name);
  console.log("getting ready to say bye....");
  bye();
}

function greet2(name) {
  console.log(`how are you, ${name}?`);
}

function bye() {
  console.log(`ok bye👋`);
}

greet("olive🌵");

위의 함수 호출 스택 결과는 아래 그림과 같다

재귀함수에서 호출 스택 사용

function factorial(x) {
  if (x === 1) {
    return 1;
  } else {
    return x * factorial(x - 1);
  }
}
console.log(factorial(3)); //6

요약

• 재귀는 함수가 스스로를 호출하는 것

• 모든 재귀 함수는 기본 단계와 재귀 단계 두부분으로 나누어져 있다.

• 스택에는 push 와 pop이라는 두가지 연산이 있다.

• 모든 함수 호출은 호출 스택을 사용한다.

• 호출 스택은 너무 커져서 메모리를 엄청나게 소비할 수 있다.
  ( 이런경우 반복문을 써서 코드를 작성하면 된다)

---

참고

'Hello Coding 알고리즘' 책을 공부하여 요약정리한 내용입니다.