5장. 프로시저, 서브루틴, 함수, 스택

한 권으로 읽는 컴퓨터 구조와 프로그래밍을 읽고 스터디를 위해 정리한 글입니다.😀

 

1. 함수 ( 프로시저, 서브루틴)

- 프로시저, 서브루틴은 함수와 동일한 말

 

1-1. 함수가 동작하는 방법

- 함수는 실행하고 리턴해야함

- 함수 리턴하는 과정

• retrurn 할 주소를 105로 설정 (프로그램 카운터라는 곳 안에 메모리 주소가 들어있음)
• 함수 실행해서 계산하기
• 미리 설정해놓은 105주소로 돌아가기

이러한 과정에는 상당히 많은 작업 필요 -> 대부분의 기계가 이런 과정을 돕는 명령어 제공

(ex)ARM 프로세서에서 Branch with link 명령어 (함수를 실행하는 명렁어와 다음 위치를 저장하는 명령어를 하나로 합친 것)

 

 

2. 스택

- 재귀함수

• 함수가 자기 자신을 호출하는 것
• 예시 코드에서 pow() 안에 pow()를 또 사용.

function pow(x, n) {
  if (n == 1) {
    return x;
  } else {
    return x * pow(x, n - 1);
  }
}

alert( pow(2, 3) ); // 8

 

• 예제  : 이미지 압축
• 재귀적 분할(함수 안에 함수 넣어서 분할) 사용

 

• 분할함수 -> 네 부분으로 나눠서 각 부분을 검사 (1픽셀짜리 조각이 생길 때 까지)
• 재귀함수 -> subdivide 함수 안에서 또 subdivide 함수를 사용함.

 

 

- 트리 구조

• subdivide 함수가 실행된 모습을 나타낸 트리

• 맨 윗 부분은 잎 노드(leaf node)

 

- 쿼드 트리

• 각 노드에서 가지가 4개 뻗어나감 (그림에서 가지가 뻗어나가는 사각형 부분을 노드라고 함)

 

- subdivide를 실행할 때의 패턴

• 깊이 우선 순회(DFS) 방식 : 트리 아래로 내려 갈 수 있으면 항상 아래로 내려가고, 더 이상 아래로 내려갈 화살표가 없는 경우에만 옆에 있는 화살표로 넘어감
• 너비 우선 순회(BFS) 방식 : 옆에 있는 화살표를 먼저 방문하고 그 후 아래쪽으로 가는 화살표를 방문하는 방식

 

 

• 트리에서 한 번 내려갈 때마다 돌아올 위치를 기억하고, 다시 원래위치로 돌아오면 기억해놨던 위치 삭제

 

- 스택 : 필요한 것은 기억해서 쌓아놓는 역할을 하는 구조

• 함수를 실행하면 리턴 될 주소와 함께 실행 순서대로 스택에 쌓임.
• 실행이 완료되면 맨 위 부터 삭제한다.

 

- push : 스택에 데이터를 넣는 것(쌓이는 것)

- pop: 스택에서 데이터를 빼는 것

- 스택 오버플로 : 더이상 데이터가 쌓일 공간이 없을 때

- 스택 언더플로 : 스택이 비어있는데(데이터가 없는데) 데이터를 스택에서 빼려고 하는 경우 

 

 

• 이러한 스택은 subdivide 예제에서도 리턴해야할 주소를 기억하기 위해 스택이 사용됨 (주소 뿐만 아니라 변수 저장에도 사용됨)
• 스택은 아주 중요하기 때문에 대부분의 컴퓨터 하드웨어는 스택을 지원함
• 소프트웨어로는 스택 오버플로 상황을 항상 검사하지 않아도 되도록 돕는 한계 레지스터가 있음

 

- 예외 : 소프트웨어가 스택 오버플로 같은 상황을 만나는 상황에서 발생

 

- 그림 5-5 스택 프레임 : 함수가 실행될 때마다 변수와 리턴할 주소가 같이 저장됨을 표현

 

- 한국어도 스택 기반 언어

• 명사(목적어) 스택에 쌓고, 그 다음 스택으로 동사를 스택에 쌓는 식.

- 여러가지 수식 표기법

• 중위 표기법 4 + 8, (1+2)x(3+4) (연산자가 피연산자 사이에)
• 전위 표기법 x+12+34 (연산자를 피연산자 앞에)
• 역 폴란드 표기법 12 + 34 +x (연산자를 피연산자 뒤에)

 

 

 

 

 

 

참고

https://velog.io/@lucky-korma/DFS-BFS%EC%9D%98-%EC%84%A4%EB%AA%85-%EC%B0%A8%EC%9D%B4%EC%A0%90

https://ko.javascript.info/recursion