[재귀함수와 스택 프레임]이진수 출력

문제

10진수 N이 입력되면 2진수로 변환하여 출력하는 프로그램을 작성하세요.

단, 재귀 함수를 이용해서 출력해야 합니다.

 

문제풀이

스택 프레임(Stack Frame)

• 메모리의 스택(stack) 영역은 함수의 호출과 관계되는 지역 변수와 매개 변수가 저장되는 영역

   ▶ JS: 콜 스택(Call Stack)에 적재되는 함수와 관련된 정보는 함수 렉시컬 환경(Functional Lexcial Environment)을

       구성하는 컴포넌트 중 하나인 함수 환경 레코드(Functional Environment Record)에 저장된다. 

       함수 환경 레코드는 매개변수, arguments 객체, 함수 내부에서 선언한 지역 변수와 중첩 함수를 등록하고 관리한다.

• 스택 영역은 함수의 호출과 함께 할당(push)되며, 함수의 호출이 종료되면 소멸(pop)
• 함수가 호출되면 스택에는 함수의 매개변수, 호출이 끝난 뒤 돌아갈 반환 주소값, 함수에서 선언된 지역 변수 등이 저장
• 스택 영역에 차례대로 저장되는 함수의 호출 정보

  ▶ 호출이 끝난 뒤 돌아갈 반환 주소값을 어떻게 기억할까?

      스택(Stack)은 자료 구조(Data Structure)의 한 종류이며 두 개의 포인터로 많은 양의 데이터를 효과적으로 관리한다.

      베이스 포인터(Base Pointer, BP)를 기준으로 데이터가 추가될 때마다 순서대로 쌓아 올리는 구조이며 새로운 데이터가

      추가될 위치를 스택 포인터(Stack Poiner, SP)가 가리키게 된다.

 

      새로운 함수를 호출하기 위해 제일 먼저 해야 할  일은 이후 함수가 호출이 끝났을 때 다시 현재 함수의 실행 위치(이후 함수

      를 호출한 다음 행)로 돌아오기 위해서 현재 실행 위치를 기억하는 인스트럭션 포인터(Instruction Pointer, IP) 레지스터

      값을 스택에 저장하는 것이다.

동작 원리

---

재귀 함수(Recursion Function)

• 컴퓨터 공학에 있어서 재귀는 자신을 정의할 때 자기 자신을 재 참조하는 방법을 뜻함
• 재귀 함수란 어떤 함수에서 자신을 다시 호출하여 작업을 수행하는 방식의 함수를 의미
• 함수 내에서 다시 자신을 호출한 후 그 함수가 끝날 때까지 함수 호출 이후의 명령문이 수행되지 않음
• 종료 조건이 함수 내에 반드시 포함되어 무한 루프를 방지해야 함

코드

function solution(n) {
  let answer = 0;

  function recursion(num) {
    if(num === 1 || num === 0) {
      return String(num);
    }
    else return recursion(Math.floor(num / 2)) + String(num % 2); //숫자 + 문자 => 문자 우선
  }
  answer = recursion(n);
  return answer;
}

console.log(solution(11));

---

function solution(n) {
  let answer = "";

  function recursion(num) {
    if(num === 0) return;
    else {
      recursion(Math.floor(num / 2));
      answer += String(num % 2);
    }
  }

  recursion(n);

  return answer;
}

console.log(solution(11));