2022/03/24) 1. 재귀함수 [재귀함수와 완전탐색(DFS:깊이우선탐색)]

1. 문제

<재귀함수>
: 자연수 N이 입력되면 재귀함수를 이용하여 1부터 N까지를 출력하는 프로그램을 작성한다.

2. 해결 방법

! 재귀함수란?

• 프로그래밍에서 재귀란 자신을 정의할 때 자기 자신을 재참조하는 것을 말한다. 따라서 재귀 함수란 함수가 호출되어 실행할 때, 함수 내부에서 자기 자신을 다시 호출하는 재귀 호출의 형태를 말한다.

! call stack(호출 스택)과 스택 프레임

• 자바스크립트는 단일 스레드 프로그래밍 언어이므로, 단일 호축 스택이 있다.(하나의 일만 처리할 수 있다는 뜻임) 호출 스택이란 함수의 호출을 기록하는 자료구조인데, 함수를 실행하면 해당 함수의 기록을 스택 맨 위에 추가(push)하고, 함수 결과값을 반환하면 스택에 쌓여있던 함수는 제거(pop)된다.
  return(반환)을 해야 스택에 쌓여있던 것(스택 프레임)이 사라진다!!
• 호출 스택의 각 항목을 스택 프레임이라고 한다. 스택프레임에는 함수의 매개변수와 호출이 끝난 후 돌아갈 복귀 주소값, 함수의 지역변수 등이 저장된다.

DFS(3)->DFS(2)->DFS(1)->return(종료)->console.log(1)->console.log(2)->console.log(3)이 되는 이유를 설명해보자.
또한 만약 console의 위치가 함수를 호출하기 전이였다면 1->2->3 순이 되었을 것이다.

3. 정답

        <script> //
            function solution(n){
                function DFS(L){
                    if(L==0) return;
                    else{
                        DFS(L-1);
                        console.log(L);   
                    }
                }
                DFS(n);
            }
            solution(3);
        </script>