제어흐름- 반복과 재귀

루프

프로그램에서 문장이나 연산이 반복되는 부분.
반복부의 문장은 부수효과를 반복하는 것이 주요한 목적이다.

부수효과가 없는 반복은 의미 없다.
어디선가의 메모리가 갱신되는것이 목적이다.

순차나열

주어진 집합의 모든 값에 대하여 한번씩 수행되는 반복문.
반복횟수는 시작 전에 결정된다.

r1 := first
r2 := step
r3 := last
L1: if r1 > r3 goto L2
. . . ––루프 몸체부. r1을 루프 인덱스를 위해 사용한다.
r1 := r1 + r2
goto L1
L2: □

 

r1 := first
r2 := step
r3 := last
goto L2
L1: . . . ––loop body; use r1 for i
r1 := r1 + r2
L2: if r1 ≤ r3 goto L1

위와 아래의 방법중 어느 방법이 더 빠를까?
1은 goto가 2번, 2는 goto가 1번이기 때문에(한번의 조건분기만을 가짐) 2가 더 효율적이다.

반복 횟수를 미리 계산할 수 있다면 프로세서의 명령문에서 반복횟수 값이 감소하고 0인지 검사하기 때문에 점프가 한 사이클로 가능한 경우가 많다. 따라서 매우 효율적인 코드가 된다.
또한 최종값의 오버플롱 위험을 방지할 수 있다.

 

논리적으로 제어되는루프

 

진위 조건식의 값이 바뀔 때 까지 반복.
루프 안에서 어떤 값을 바꾸어서 조건식의 값이 바뀌게 됨.

 

반복자(Iterator)

 

반복자란 루프를 돌리기 위해 대상이 되는 미리 정해진 집합을 차례로
한개씩 돌려주는 기능이다.

C++과 Java는 반봅자 객체를 표준 인터페이스로 정했고, 참 반복자와 유사하게 라이브러리로 구현된다.

• 참 반복자

참 반복자란 모든 컨테이너의 추상기능으로 소속 아이템에 대한 반복자를 제공할 수 있게 한다.
루프몸체와 대상이 되는 값을 제공하는 부분을 구분하고, yield문을 통해 값을 하나씩 제공해준다.
또한 별도의 스레드처럼 동작한다.

 

여기서 알아야 할 것은 yield이다.
yield가 호출될 때 마다 차례로 다음 값을 반환한다. 다음 호출 때는 이전 호출상태에서 이어서 다음 값을 계산한다.
반복자가 더 이상 생성할 값이 없을 때는 그냥 return한다.
루프의 인덱스 값을 하나씩 생성을 해주는 것이며 값을 요청을 하면 이를 보내고 나서 멈추는 것이다.
즉, 반복과 값을 사용하는 것이 독립적인 코드로 돌도록 하는 것이다.

자바는 이러한 yield를 지원하지 않는다.

자바의 반복자 객체는 초기화, 다음 값의 생성, 종료 검사를 담당한다.

class TreeNode<T> implements Iterable<T> {
TreeNode<T> left;
TreeNode<T> right;
T val;
...
public Iterator<T> iterator() {
return new TreeIterator(this);
}
private class TreeIterator implements Iterator<T> {
private Stack<TreeNode<T>> s = new Stack<TreeNode<T>>();
TreeIterator(TreeNode<T> n) {
s.push(n);
}
public boolean hasNext() {
return !s.empty();
}
public T next() {
if (!hasNext()) throw new NoSuchElementException();
TreeNode<T> n = s.pop();
if (n.right != null) s.push(n.right);
if (n.left != null) s.push(n.left);
return n.val;
}
public void remove() {
throw new UnsupportedOperationException();
}
}

Iterable인터페이스를 지원해야 하며, 그 인터페이스는 Iterator객체를 반환하는 iterator() 메소드를
포함한다. Iterator객체는 마지막으로 돌려준 위치와 상태를 기억해야하고 그 다음부터 이어서 수행하기 위한
데이터를 모두 객체에 저장해야 한다.

재귀

반복은 주어진 연산과 문장 부분을 반복하여 수행하며, 변수의 반복적인 수정에 의해
계산이 이루어진다. 재귀는 부수효과가 없는 함수형 언어에서 보다 자연스럽다.

• 변수 값을 바꾸는 대신 함수에 매개변수로 전달되는 값을 바꾸면서 계속 호출한다.
• 단계적으로 계산된 값이 반환된다.

꼬리재귀

 

반복은 서브루팅호출과 스택관리 때문에 재귀보다 더 효율적이다.
재귀적 구현이 실제 서브루틴호출을 일으키고 실행 시간 스택에 지역변수와 북키핑 정보를 위한 공간을 할당하는 정상적인 함수 호출을 하기 때문이다.

 

최적화 컴파일러는 이런 경우 재귀적 함수에 대해 아주 훌륭한 코드를 생성할 수 있다. 특히 gcd 예처럼 꼬리 재귀가 가능한 경우가 특히 그렇다. 그런 함수에 대해서는 동적으로 할당되는
스택 공간이 불필요하다. 컴파일러는 현재의 반복부에 할당된 공간을 재사용하여
재귀적 호출을 일어나게 할 수 있다.

꼬리재귀란 재귀 이전에 필요한 계산을 모두 마치고, 재귀 호출에서 리턴된 값을 그대로 반환하는것이다.

꼬리재귀는 반복으로 변경이 가능하다.

꼬리재귀는 스택할당 방식이 아니라 반복으로 변환하여 컴파일 하기때문에 효율적이다.

int gcd(int a, int b) {
/* assume a, b > 0 */
start:
if (a == b) return a;
else if (a > b) {
a = a-b; goto start;
} else {
b = b-a; goto start;
}
} 

적용적순서

 

아규먼트 계산을 함수 호출전에 한다. 이후 결과값만 전달한다.

정규적 순서

지연계산. 수식이 필요할 때 계산한다(아규먼트의 수식을 그대로 넘긴다...

보통 적용적 순서가 명확하고 빠르기때문에 대부분의 언어에서 선택된다.

그럼에도 적용적 순서에서 안되는 것을 정규적 순서로 하면 되는 경우가 있다.
아규먼트중에 오류를 일으키거나 무한 계산이 필요한 것이 있을때 실제 그 값이 필요하지 않을 수도 있다.
불필요한 계산을 피해서 성능이 향상될 수 있다.

yield로 정규순서의 일종이다.