함수 == 프로시저 == 서브루틴
- 코드를 재사용 하는 주요 수단입니다.
- 중복된 코드를 줄여서 코드가 메모리를 덜 차지합니다.
- 코드에 버그가 있는 경우 한 군데만 고치면 됩니다.
함수를 호출하는 부분에서 함수를 실행하고 다시 원래 자리로 돌아올 방법이 필요합니다.
레지스터(Register)
- CPU 내부에서 처리할 명령어나 연산의 중간 결과값 등을 일시적으로 기억, 임시기억장소
- 메모리 중 가장속도가 빠름
- 플립플롭이나 래치들을 병렬연결하여 구성
- 레지스터 간의 자료 전송은 직렬전송, 병렬전송, 버스전송 등으로 구성
주요 레지스터의 종류 :
프로그램 카운터
- 프로그램 카운터(Program counter, PC)는 마이크로프로세서(중앙 처리 장치) 내부에 있는 레지스터 중의 하나로서, 다음에 실행될 명령어의 주소를 가지고 있어 실행할 기계어 코드의 위치를 지정한다. 때문에 명령어 포인터라고도 한다.
if( 6 > 3 ) {
출력 6;
}해당 프로그램 카운터의 작동예시
범용레지스터란?
책에서의 예시(세제곱 할 값을 구하는 함수)
이러한 과정에서 상당히 많은 작업이 필요한데, 대부분의 기계는 이런 과정을 돕는 명령어를 제공한다고 합니다. ARM 프로세서에서는 링크 레지스터를 사용해 분기 명령어가 있는데, 이는 함수를 호출하는 명령어와 현재 명령어의 다음 위치를 저장하는 명령어를 하나로 합친것 입니다.
재귀
함수가 자기 자신을 호출하는 것을 재귀(recursion)라고 하고, 재귀적 분할을 위한 이미지 압축이 책에 예제로 제시되어있습니다.
(subdivide 함수안에서 subdivide 함수를 호출하는걸 확인할 수 있습니다.)
트리
트리 구조(tree 構造, 문화어: 나무구조)란 그래프의 일종으로, 여러 노드가 한 노드를 가리킬 수 없는 구조입니다. 간단하게는 회로가 없고, 서로 다른 두 노드를 잇는 길이 하나뿐인 그래프를 트리라고 부릅니다. 수학에서 유향 비순환 그래프(DAG, directed acyclic graph)라고 부릅니다.
- 위에 그래프에서 네모의 숫자가 원래 이미지의 픽셀 수인 64보다 적은 40임을 알 수 있고, 이는 저장해야 할 정보가 줄어든다는 뜻입니다.
- 위와같이 각노드에서 가지가 4개 뻗어나가기 때문에 쿼드트리(quadtree)라고 부릅니다.
- 쿼드트리는 공간데이터 구조(spatail data structure)에 속합니다.
재귀 함수가 제대로 작동하려면 반환 주소를 여럿 저장할 수 있어야 합니다.
이미 들어있던 반환값을 덮어씌워 버리게되면 재귀의 의미가 없기때문입니다.
- 위에 트리에서 내려갈 수 있을때는 항상 내려가고, 더이상 내려갈 수 없는 경우에만 옆의 화살표로 넘어가는 것을 깊이 우선 순회(depth-frist traversal) 라고 합니다.
- 옆에 있는 화살표를 먼저 방문하고 그 후 아래쪽으로 가는 방식을 너비 우선 순회(breadth-first traversal)라고 합니다.
스택
스택의 기본 구조
- 스택에 물건을 푸시(push)해서 넣고, 스택에서 물건을 팝(pop)해서 제거합니다.
- 스택에 물건을 푸시할때 더이상 들어갈 공간이 없으면 스택 오버플로(stack overflow)라고 합니다.
- 빈 스택에서 물건을 가져오는 경우를 스택 언더플로(stack underflow)라고 합니다.
- 대부분의 스택을 지원하는 컴퓨터 하드웨어는 스택 오버플로를 항상 검사하지 않아도 되도록 돕는 한계 레지스터(limit register)를 포함합니다.
-
함수가 호출될 때마다 스택에 저장되어있는 데이터의 모음을 스택 프레임(stack frame)이라고 부릅니다. 아래는 책에서의 스택프레임 예시입니다.
-
포스(forth)나 포스트스크립트(PostScript)같은 몇몇 언어와 옛날 HP 계산기 몇 가지는 스택 기반 언어입니다.
-
일본어나 한국어도 스택 기반 언어라고 합니다.
-
중위 표기법, 전위 표기법, 폴란드 표기법, 역 폴란드 표기법 등의 내용이 있습니다. 그중 역폴란드 표기법(RPN)은 스택으로 쉽게 구현 가능합니다.
