재귀와 스택
함수가 필요에 의해 자기 자신을 호출할 때 이를 재귀 라 부름
큰 목표 작업 하나를 동일하면서 간단한 작업 여러 개로 나눌 때
목표 작업을 간단한 동작 하나와 목표 작업을 변형한 작업으로 단순화 시킬 때
-
재귀와 반복
간단한 작업을 여러 번 행할 때 둘다 사용 가능한 경우 많음
재귀를 이용해 작성한 모드는 반복문을 사용한 코드로 다시 작성 가능
-
반복
반복적인 사고를 통한 방법
-
재귀
작업을 단순화 하고 자기 자신을 호출
코드를 두갈래에서 여러 갈래로 나누어 실행
함수호출의 결과가 명확해질 떄 까지 간단한 함수 호출로 계속 줄이기 가능
실행 컨텍스트 때문에 메모리 차지 주의 필요
조건에 따라(조건에 따라 다른 재귀 서브 호출하거나 다른 분기문 얽혀있을 때) 재귀와 반복이 큰 차이 없을 수도 있음
-
재귀의 베이스
명확한 결괏값을 즉시 도출
-
재귀 단계
목표 작업을 간단한 동작과 목표 작업을 변형한 작업으로 분할 한 것.
수학식으로도 표현 가능
-
재귀 사용한 코드 짧음
반복적 사고에 근거하여 작성한 코드보다 대개 짧음
-
재귀 깊이
가장 처음 하는 호출을 포함한 중첩 호출의 최대 개수
JS 엔진은 최대 재귀 깊이 제한
-
-
-
실캥 컨텍스트와 스택
재귀 호출이 함수 실행에 대한 세부 정보를 담고 있는 내부 데이터 구조
제어 흐름의 현재 위치, 변수의 현재 값, this의 값, arguments 등 상세 내부 정보 저장
함수 호출 1 회당 정확히 하나의 실행 컨텍스트 생성
스택 구조로 형성되어 처리
실행 컨텍스트는 메모리를 차지
-
함수 내부의 중첩 호출시 절차
-
현재 함수의 실행 중지
-
중지된 함수와 연관된 실행 컨텍스트를 실행 컨텍스트 스택 이라는 특별한 자료 구조에 저장
-
중첩 호출 실행
-
중첩 호출 실행 끝난 후 실행 컨텍스트 스택에서 일시 중단한 함수의 실행 컨텍스트 꺼내 옴
-
중단한 함수 실행 다시 이어감
-
-
-
재귀적 순회
재귀로 구현할 때 좋음
-
반복문
복잡한 자료구조를 돌 떄 중첩 반복문 구조 여러개 필요해서 코드가 복잡해 짐
-
재귀
하위 자료 구조의 깊이와 상관 없이 원하는 값을 얻을 수 있음
-
-
재귀적 구조
자기 자신의 일부를 복제하는 형태의 자료 구조
HTML 태그나 XML 도 재귀적 자료 구조 형태.
-
연결 리스트
객체를 정렬하여 저장할 때 사용
배열의 인덱싱 연산 수행이 길어졌을 때 대체해서 사용
요소를 나누기, 다시 합치기, 추가, 삭제가 쉬워짐
가비지 컬렉션 이용 가능
인덱스에 접근할 수 없는 단점 있음
중간에 요소 삽입이나 삭제 하는 연산 없을 시 큐 나 데크 사용 가능
-
요소
value : 값
next : 다음 연결 리스트 요소를 참조하는 프로퍼티. 없을 땐 null
-
개선
이전 요소를 참조하는 프로퍼티 추가
리스트 마지막 요소 참조하는 변수 추가 가능(단 리스트 갱신 시 tail도 갱신 필요)
요구사항에 따라 구조 변경 가능
-
-
요약
-
함수가 필요에 의해 자기 자신을 호출하는 경우를 재귀 라고 부름
-
재귀와 반복은 서로 대체 가능한 경우가 많음
-
재귀는 실행 컨텍스트 사용
-
베이스는 명확한 결과값을 즉시 도출하는 코드
-
재귀 단계는 목표 작업을 간단한 동작과 목표 작업을 변형한 작업으로 분할한 것
-
재귀 깊이는 처음 호출을 포함한 중첩 호출의 최대 개수
-
실행 컨텍스트는 함수 실행에 대한 세부 정보 담고 있는 내부 데이터 구조. (제어 흐름의 현재 위치, 변수의 현재 값, this 의 값 등 저장됨)
-
실행 컨텍스트는 실행 컨텍스트 스택에 저장
-
재귀적 순회는 재귀로 구현할 떄 좋음
-
재귀적 구조는 자기 자신의 일부를 복제하는 형태의 자료 구조
-
연결 리스트로 list 자료형 대체 가능하지만 단점도 있음