2023. 11. 28. 21:35ㆍ프로그래밍 공부/OOP
13.1 재귀적 void 함수
재귀(Recursion)
C++에서 함수의 정의는 정의하고자 하는 함수에 대한 호출을 포함할 수 있다.
그런 경우 함수는 재귀적(recursive)이라고 한다.
예: 수직적 숫자
디스플레이 13.1에는 writeVertical이라는 재귀 함수에 대한 데모 프로그램이 포함되어 있다.
이 함수는 하나의 (음이 아닌) 정수 인수를 사용하여 화면에 해당 정수를 기록하며, 숫자는 한 줄당 한 줄씩 내려간다.
예를 들어
호출
writeVertical(1234);
은 다음 결과물을 생산할 것이다
1
2
3
4
writeVertical이 수행할 작업은 다음 두 가지 경우로 나눌 수 있다:
■ 간단한 경우: n < 10이면 숫자 n 을 화면에 적는다.
결국, 숫자의 길이가 한 자리밖에 되지 않는다면, 그 일은 사소한 것이다.
■ 재귀적인 경우: n > = 10인 경우 두 가지 하위 작업을 수행한다:
1. 마지막 자리를 제외한 모든 자리를 출력한다.
2. 마지막 자리를 출력한다.
예를 들어 인수가 1234인 경우 첫 번째 하위 작업이 출력된다
1
2
3
두 번째 하위 작업은 4를 출력한다.
이렇게 하위 작업으로 분해하면 함수 정의를 도출할 수 있다.
하위 작업 1은 원래 작업의 더 작은 버전이므로 재귀적 호출로 이 하위 작업을 구현할 수 있다.
하위 작업 2는 앞서 나열한 간단한 경우이다.
따라서 매개 변수 n이 있는 writeVertical 함수에 대한 알고리즘 개요는
다음 의사 코드에 의해 제공된다:
if (n < 10)
{
cout << n << endl;
}
else //n은 두 자리 이상이다:
{
writeVertical(끝자리가 제거된 숫자 n); //재귀적 서브태스크
cout << n의 마지막 자리 << endl;
}
다음과 같은 특징들을 관찰하면
이 의사 코드를 완전한 C++ 함수 정의로 변환하기 쉽다:
n / 10은 끝자리를 뺀 n이다.
n % 10은 n의 마지막 자리이다.
예를 들어, 1234/10은 123으로 평가되고 1234% 10은 4로 평가된다.
함수의 전체 코드는 다음과 같다:
void writeVertical( int n)
{
if (n < 10)
{
cout << n << endl;
}
else //n is two or more digits long:
{
writeVertical(n / 10);
cout << (n % 10) << endl;
}
}
디스플레이 13.1 재귀적 void 함수
//Program to demonstrate the recursive function writeVertical.
#include <iostream>
using std::cout;
using std::endl;
void writeVertical( int n);
//Precondition: n >= 0.
//Postcondition: The number n is written to the screen vertically,
//with each digit on a separate line.
int main( )
{
cout << "writeVertical(3):" << endl;
writeVertical(3);
cout << "writeVertical(12):" << endl;
writeVertical(12);
cout << "writeVertical(123):" << endl;
writeVertical(123);
return 0;
}
//uses iostream:
void writeVertical(int n)
{
if (n < 10)
{
cout << n << endl;
}
else //n is two or more digits long:
{
writeVertical(n / 10);
cout << (n % 10) << endl;
}
}
샘플 대화 상자
writeVertical(3):
3
writeVertical(12):
1
2
writeVertical(123):
1
2
3
재귀적 호출 추적
다음 함수 호출이 실행될 때(디스플레이 13.1과 같이) 정확히 어떻게 되는지 알아보겠다:
writeVertical(123);
이 함수 호출이 실행되면 컴퓨터는 어떤 함수 호출도 그대로 진행한다.
인수 123이 매개 변수 n으로 치환되고, 함수의 본문이 실행된다.
123이 n으로 치환된 후, 실행되는 코드는 다음과 같다:
if (123 < 10)
{
cout << 123 << endl;
}
else //n is two or more digits long:
{
writeVertical(123 / 10); // 재귀 호출이 돌아올 때까지 계산이 여기서 중지된다.
cout << (123 % 10) << endl;
}
123은 10 이상이므로 나머지 부분은 실행된다.
그러나 다른 부분은 함수 호출 writeVertical(n / 10); 로 시작한다.
이 함수는 (n은 123과 같으므로) 호출 writeVertical(123 / 10); 이다.
그리고 이것은 writeVertical(12); 과 동등하다.
실행이 이 재귀 호출에 도달하면
현재 함수 계산이 일시 중지되고 재귀 호출이 실행된다.
이 재귀 호출이 끝나면
일시 중지된 계산의 실행은 이 시점으로 되돌아가고
일시 중지된 계산은 그 시점부터 계속된다.
재귀적 호출
writeVertical(12);
는 다른 함수 호출과 마찬가지로 처리된다.
인수 12가 매개 변수 n으로 대체되고, 함수의 본문이 실행된다.
n으로 12를 대체한 후, 다음과 같은 두 개의 계산이 있다:
if (12 < 10)
{
cout << 12 << endl;
}
else //n is two or more digits long:
{
writeVertical(12 / 10); //재귀 호출이 돌아올 때까지 계산이 여기서 중지된다.
cout << (12 % 10) << endl;
}
12는 10보다 작지 않기 때문에 다른 부분이 실행된다.
그러나 이미 보신 것처럼 다른 부분은 재귀적 호출로 시작한다.
재귀적 호출에 대한 인수는 n / 10 이며, 이 경우 12 / 10에 해당한다.
따라서 writeVertical 함수의 두 번째 계산은 중단되고 다음 재귀적 호출이 실행된다:
writeVertical(12 / 10);
은 다음과 같다
writeVertical(1);
이 시점에서 두 개의 일시 중단된 연산들이 다시 시작되기를 기다리고 있고,
컴퓨터는 이 새로운 재귀적 호출을 실행하기 시작하며,
이것은 이전의 모든 재귀적 호출들과 똑같이 처리된다.
인수 1은 매개 변수 n으로 치환되고, 함수의 본문이 실행된다.
이 시점에서 계산은 다음과 같다:
if (1 < 10) // 이번에는 재귀 호출이 없다
{
cout << 1 << endl;
}
else //n is two or more digits long:
{
writeVertical(1 / 10);
cout << (1 % 10) << endl;
}
이번에 함수의 본문이 실행되면 다른 일이 발생한다.
1이 10보다 작으므로 if-else 문에서의 부울 식은 참이므로 다른 것 앞의 문장이 실행된다.
이 문장은 단순히 화면에 인수 1을 쓰는 cout 문장이므로
호출 writeVertical(1)은 화면에 1을 쓰고 재귀적인 호출 없이 끝난다.
호출 writeVertical(1)이 종료되면
다음과 같이 종료되기를 기다리는 일시 중단된 계산이 중단된 곳에서 다시 시작된다:
if (12 < 10)
{
cout << 12 << endl;
}
else //n is two or more digits long:
{
writeVertical(12 / 10); //계산이 여기서 다시 시작된다.
cout << (12 % 10) << endl;
}
이 일시 중단된 계산이 재개되면 12 % 10 값(2)을 출력하는 cout 문을 실행한다.
그러면 해당 계산이 종료되지만 다시 시작하기 위해 대기 중인 또 다른 일시 중단된 계산이 있다.
이 마지막 일시 중단된 계산이 재개되면 다음과 같은 상황이 발생한다:
if (123 < 10)
{
cout << 123 << endl;
}
else //n is two or more digits long:
{
writeVertical(123 / 10); //계산이 여기서 다시 시작된다.
cout << (123 % 10) << endl;
}
이 마지막으로 중단된 연산은 123%10이라는 값을 출력하는데, 이 값은 3이다.
그러면 원래 함수 호출의 실행이 종료된다.
그리고 당연히 숫자 1, 2, 3이 한 줄에 하나씩 화면에 쓰여졌다.
재귀에 대한 자세한 설명
함수의 정의 writeVertical은 재귀를 사용한다.
그러나 우리는 함수 호출 writeVertical(123)을 평가하는 데 있어서 새로운 것이나 다른 것을 하지 않았다.
우리는 이전 장에서 보았던 함수 호출들과 똑같이 그것을 처리했다.
우리는 단순히 매개 변수 n에 인수 123을 대입한 다음 함수 정의 본문에서 코드를 실행했다.
재귀 호출에 도달했을 때 우리는 재귀 호출에 도달했다
writeVertical(123 / 10);
우리는 이 과정을 그저 한 번 더 반복했을 뿐이다.
재귀가 작동하는 방법
컴퓨터는 다음과 같은 방법으로 재귀적 호출을 추적한다.
어떤 함수가 호출되면, 컴퓨터는 매개변수에 대한 인수를 연결하고 코드를 실행하기 시작한다.
재귀적 호출을 만나면, 재귀적 호출의 결과를 먼저 알아야 진행할 수 있기 때문에 계산을 일시적으로 중단한다.
나중에 계산을 계속하기 위해 필요한 모든 정보를 저장하고, 재귀적 호출을 평가하기 위해 계속 진행한다.
재귀적 호출이 완료되면, 컴퓨터는 외부 계산을 마치기 위해 되돌아온다.
재귀가 끝나는 방법
C++ 언어는 함수 정의에서 재귀적 호출이 어떻게 사용되는지에 대한 제한을 두지 않는다.
그러나 재귀적 함수 정의가 유용하기 위해서는
함수의 어떤 호출도 결국 재귀에 의존하지 않는 어떤 코드로 끝나도록 설계되어야 한다.
함수는 자신을 호출할 수 있고, 재귀적 호출은 함수를 다시 호출할 수 있다.
이 과정은 몇 번이든 반복될 수 있다.
그러나 재귀적 호출 중 하나가 결국 값을 반환하기 위해 재귀에 의존하지 않는 한 이 과정은 종료되지 않는다.
성공적인 재귀적 함수 정의의 일반적인 개요는 다음과 같다:
■ 함수가 하나 이상의 재귀 호출을 사용하여 하나 이상의 작은 버전의 작업을 수행하는 하나 이상의 경우.
■ 함수가 재귀적 호출을 사용하지 않고 임무를 수행하는 하나 이상의 경우.
재귀적 호출이 없는 이러한 경우를 기본 경우(base case) 또는 중지 경우(stopping case)라고 한다.
종종 if-else 문은 어떤 경우를 실행할지를 결정한다.
일반적인 시나리오는 원래 함수 호출이 재귀적 호출을 포함하는 경우를 실행하는 것이다.
재귀적 호출은 다른 재귀적 호출을 요구하는 경우를 다시 실행할 수 있다.
몇 번씩 재귀적 호출이 또 다른 재귀적 호출을 생성하지만, 결국에는 정지 사례 중 하나가 적용되어야 한다.
함수의 모든 호출은 결국 정지 사례로 이어져야 한다.
그렇지 않으면 재귀적 호출들의 무한 연쇄 때문에 함수 호출은 결코 끝나지 않을 것이다.
(실제로 재귀적 호출들의 무한 연쇄를 포함하는 호출은
실제로 영원히 실행되는 것이 아니라 비정상적으로 종료되는 것이 보통이다.)
중지 사례에 도달하도록 보장하는 가장 일반적인 방법은
함수를 작성하여 각 재귀 호출 시 일부 (양의) 숫자 수량을 줄이고 일부 "작은" 값에 대한 중지 사례를 제공하는 것이다.
디스플레이 13.1에 있는 writeVertical 함수를 이렇게 설계했다.
writeVertical 함수를 호출하면 그 호출은 더 작은 인수를 가진 재귀적 호출을 생성한다.
이것은 인수가 10보다 작을 때까지 각 재귀적 호출이 또 다른 재귀적 호출을 생성하면서 계속된다.
인수가 10보다 작으면 함수 호출은 더 이상 재귀적 호출을 생성하지 않고 종료되고,
이 프로세스는 원래 호출로 되돌아가서 종료된다.
재귀 함수 정의의 일반적인 형태
성공적인 재귀 함수 정의의 일반적인 개요는 다음과 같다:
■ 정의 중인 함수에 대한 하나 이상의 재귀 호출을 포함하는 하나 이상의 경우이다.
이러한 재귀적 호출은 정의되는 함수에 의해 수행되는 "더 작은" 버전의 작업을 해결해야 한다.
■ 재귀적 호출이 없는 경우를 하나 이상 포함한다.
기저 사례(Base case) 또는 정지 경우(Stopping case): 재귀적 호출이 없는 경우
함정: 무한 재귀
앞에서 설명한 함수 writeVertical의 예에서,
일련의 재귀적 호출들은 결국 재귀를 수반하지 않는 함수의 호출에 도달했다.
무한 재귀(infinite recursion): 모든 재귀적 호출이 또 다른 재귀적 호출을 생성한다면, 이론적으로 함수에 대한 호출은 영원히 실행될 것이다.
실제로 이러한 함수는 일반적으로 컴퓨터의 자원이 부족하여 프로그램이 비정상적으로 종료될 때까지 실행된다.
무한 재귀의 예)
다음은 구문론적으로 올바른 C++ 함수 정의로
대체 버전의 함수 writeVertical을 정의하려고 시도한 결과이다:
void newWriteVertical( int n)
{
newWriteVertical(n / 10);
cout << (n % 10) << endl;
}
이 함수를 호출하는 프로그램에 이 정의를 포함시키면
컴파일러가 함수 정의를 기계 코드로 변환하여 사용자가 기계 코드를 실행할 수 있다.
게다가 이 정의는 어느 정도 타당성을 가지고 있다.
인수를 newWriteVertical로 출력하려면
먼저 마지막 자리를 제외한 모든 자리를 출력하고 마지막 자리를 출력해야 한다.
그러나 이 함수를 호출하면 무한히 많은 재귀적 호출이 생성된다.
newWriteVertical(12)을 호출하면
해당 실행이 중지되어 newWriteVertical(1)과 동등한 재귀적 호출 newWriteVertical(12 / 10)을 실행한다.
재귀적 호출의 실행이 중지되어 재귀적 호출의 실행이 중지된다
newWriteVertical(1 / 10);
에 해당하는 것
newWriteVertical(0);
그러면 다시 newWriteVertical(0 / 10); 재귀 호출 실행이 중지된다.
다음과 동등하다
newWriteVertical(0);
그러면 newWriteVertical(0); 등과 같은 재귀 함수를 영원히 다시 실행하는 재귀 호출이 생성된다.
newWriteVertical의 정의에는 중지 사례가 없으므로
프로세스는 영원히(또는 컴퓨터 리소스가 부족할 때까지) 진행된다.
재귀 스택
스택
대부분의 컴퓨터 시스템은 재귀를 추적하기 위해 스택이라고 불리는 구조를 사용한다.
스택: 종이를 쌓아두는 것과 비슷한 매우 특수화된 종류의 메모리 구조
이 비유에서는 여분의 빈 종이를 무한정 공급한다.
정보를 스택에 배치하기 위해
이 종이들 중 한 장에 정보를 기록하고 그 위에 종이를 쌓는다.
더 많은 정보를 스택에 배치하기 위해
깨끗한 종이를 가져가서 정보를 기록하고 이 새로운 종이를 스택의 맨 위에 놓는다.
이렇게 간단한 방법으로 점점 더 많은 정보를 스택에 배치할 수 있다.
선출후입
스택에서 정보를 가져오는 것도 매우 간단한 절차로 수행된다.
맨 위의 종이는 읽을 수 있고 더 이상 필요하지 않을 때 버려진다.
한가지 복잡한 것이 있다:
종이의 맨 위의 시트만 접근할 수 있다.
예를 들어, 세 번째 시트를 위에서 읽으려면 맨 위의 두 시트는 버려야 한다.
스택에 마지막으로 올려진 시트가 스택에서 처음 떼어낸 시트이기 때문에
스택: 선출후입(Last In/First Out) 메모리 구조
재귀와 스택
컴퓨터는 스택을 사용하여 재귀를 쉽게 추적할 수 있다.
함수가 호출될 때마다 새로운 종이 한 장을 가져간다.
함수 정의는 이 종이 한 장에 복사되고 인수는 함수 매개변수에 연결된다.
그런 다음 컴퓨터는 함수 정의의 본문을 실행하기 시작한다.
재귀 호출이 만나면
재귀 호출에 의해 반환되는 값을 계산하기 위해
그 종이 위에서 하고 있는 계산을 중지한다.
그러나 재귀 호출을 계산하기 전에
재귀 호출에 의해 반환되는 값을 최종적으로 결정하면
중지된 계산을 계속할 수 있을 정도로 충분한 정보를 저장한다.
이렇게 저장된 정보는 종이 한 장에 기록되어 스택에 저장된다.
재귀 호출을 위해 새로운 종이 한 장이 사용된다.
컴퓨터는 이 새로운 종이 한 장에
함수 정의의 두 번째 복사본을 함수 매개변수 인수에 연결한 후
재귀 호출을 실행하기 시작한다.
재귀 호출이라 불리는 복사본 내에서 재귀 호출이 되면
스택에 정보를 저장하고 새로운 재귀 호출을 위해 새로운 종이 한 장을 사용하는 과정을 반복한다.
이 과정은 앞 절의 "재귀 호출 추적"에 설명되어 있다.
비록 우리가 그 당시에는 스택이라고 부르지 않았지만,
하나를 다른 하나의 스택 위에 놓은 계산 그림은 스택의 동작을 보여준다.
이 과정은 함수에 대한 어떤 재귀적 호출이
더 이상 재귀적 호출을 생성하지 않고 계산을 완료할 때까지 계속된다.
그렇게 되면 컴퓨터는 스택의 맨 위에 있는 종이쪽지로 관심을 돌린다.
이 시트에는 방금 끝난 재귀적 계산을 기다리는 부분적으로 완성된 계산이 들어 있다.
따라서 그 일시 중단된 계산을 진행하는 것이 가능하다.
그 일시 중단된 계산이 끝나면 컴퓨터는 그 종이를 버리고
그 아래에 있는 일시 중단된 계산이 스택의 맨 위에 있는 계산이 된다.
컴퓨터는 현재 스택의 맨 위에 있는 일시 중단된 계산 등에 관심을 돌린다.
이 과정은 맨 아래의 시트에 있는 계산이 완료될 때까지 계속된다.
재귀적 호출이 얼마나 많이 이루어지고 함수 정의가 어떻게 쓰이는지에 따라
스택은 어떤 식으로든 성장하고 축소될 수 있다.
스택의 시트는 선출후입(Last-in/First-out) 방식으로만 접근할 수 있지만,
재귀적 호출을 추적하기 위해 필요한 것은 바로 그것이다.
각 일시 중단된 버전은 스택에서 바로 위에 있는 버전의 완료를 기다리고 있다.
활성화 프레임
말할 필요도 없이 컴퓨터에는 종이가 쌓여 있지 않는다.
이것은 그저 비유일 뿐이다.
컴퓨터는 종이 조각이 아니라 메모리의 일부분을 사용한다.
활성화 프레임(activation frame): 메모리의 이러한 일부분 중 하나("종이 조각")의 내용, 스택에 저장되는 것
이 활성화 프레임들은 방금 논의한 선출후입(Last In/First Out)으로 처리된다.
이 활성화 프레임들은 함수 정의의 전체 복사본을 포함하는 것이 아니라
단지 함수 정의의 단일 복사본을 참조하는 것이다.
그러나 활성화 프레임은 컴퓨터가 활성화 프레임이 함수 정의의 전체 복사본을 포함하는 것처럼 행동할 수 있도록 충분한 정보를 포함한다.
스택
스택(stack): 선출후입(Last-in/First-out) 메모리 구조
스택에서 참조되거나 제거된 첫 번째 항목은 항상 스택에 입력된 마지막 항목이다.
스택은 컴퓨터에서 재귀를 추적하기 위해 사용된다.
함정: 스택 오버플로우
스택의 크기에는 항상 일정한 한계가 있다.
만약 함수가 자신에게 재귀적인 호출을 하는 긴 연쇄이 존재한다면,
그 호출로 인해 또 다른 재귀적 호출이 발생하고,
그 호출로 인해 또 다른 재귀적 호출이 발생하는 등의 문제가 발생하면,
이 체인의 재귀적 호출은 또 다른 활성화 프레임을 스택에 설치하게 된다.
만약 이 연쇄가 너무 길다면,
스택은 그 한계를 넘어서서 증가하려고 할 것이다.
스택 오버플로우(stack overflow): 스택이 스택의 크기의 한계를 넘어서서 증가할 때 일어나는 오류 조건
만약 당신이 "스택 오버플로우"라는 오류 메시지를 받는다면,
어떤 함수 호출이 지나치게 긴 재귀적 호출을 생성했을 가능성이 높다.
스택 오버플로우의 한 가지 흔한 원인은 무한 재귀이다.
함수가 무한히 재귀적이면,
결국 스택이 어떤 스택 크기 제한을 초과하도록 만들려고 할 것이다.
재귀 대 반복
반복 버전
재귀가 반드시 필요한 것은 아니다.
사실 일부 프로그래밍 언어에서는 이를 허용하지 않는다.
재귀를 사용하여 수행할 수 있는 모든 작업은 재귀를 사용하지 않고 다른 방법으로 수행할 수도 있다.
예) 디스플레이 13.2는 디스플레이 13.1에 주어진 함수의 비재귀적 버전을 포함한다.
비재귀적 버전의 함수는 일반적으로 재귀 대신 어떤 종류의 반복문(들)을 사용한다.
반복 버전(iterative version): 재귀 대신 일련의 반복문(들)을 사용하는 비재귀적 버전(nonrecursive version)
만약 디스플레이 13.1에 주어진 함수 writeVertical의 정의가 디스플레이 13.2에 주어진 버전으로 대체된다면 출력은 동일할 것이다.
이 경우에 사실처럼 재귀적 버전의 함수는 반복 버전보다 훨씬 간단하고 우아할 수 있으므로 효율성의 향상이 항상 좋은 것은 아니다.
꼬리 재귀
대부분의 최신 컴파일러들은 자동으로 어떤 단순 재귀 함수들을 같은 반복 함수로 변환해 줄 것이다.
꼬리 재귀(tail recursion)를 사용하는 함수: 재귀 호출 후에 더 이상의 계산이 일어나지 않는다는 특성을 가지며, 함수는 즉시 반환된다.
다음 절에서 값을 반환하는 재귀 함수들을 다룰 때, 재귀 호출의 값을 수정하지 않고 반환하는 함수는 꼬리 재귀 함수가 된다.
그런 경우 꼬리 재귀 함수는 쉽게 같은 반복 해로 변환될 수 있다.
컴파일러의 설명서와 최적화 플래그들을 확인하여 이 연산이 사용 가능한지 확인하자.
꼬리 재귀적이 아닌 재귀적으로 작성된 함수는
보통 동작 속도가 느리고 반복되는 동등한 버전보다 더 많은 스토리지를 사용한다.
재귀를 추적하려면 컴퓨터가 스택을 조작하는 데 상당한 노력을 기울여야 한다.
하지만 시스템이 이 모든 작업을 자동으로 해주기 때문에
재귀를 사용하면 이해하기 쉬운 코드를 생성하여 프로그래머로서의 직업이 더 쉬워질 수도 있다.
디스플레이 13.2 디스플레이 13.1의 함수 반복 버전
//Uses iostream:
void writeVertical( int n)
{
int nsTens = 1;
int leftEndPiece = n;
while (leftEndPiece > 9)
{
leftEndPiece = leftEndPiece / 10;
nsTens = nsTens * 10;
}
//nsTens is a power of ten that has the same number
//of digits as n. For example, if n is 2345, then
//nsTens is 1000.
for ( int powerOf10 = nsTens;
powerOf10 > 0; powerOf10 = powerOf10 / 10)
{
cout << (n / powerOf10) << endl;
n = n % powerOf10;
}
}
13.2 값을 반환하는 재귀 함수
값을 반환하는 재귀 함수의 일반 형식
지금까지 살펴본 재귀 함수들은 모두 void 함수들이지만 재귀가 void 함수에만 국한되는 것은 아니다.
재귀 함수는 어떤 종류의 값이든 반환할 수 있다.
값을 반환하는 재귀 함수를 설계하는 기법은 기본적으로 void 함수의 경우와 동일하다.
값을 반환하는 재귀 함수 정의의 개요는 다음과 같다:
■ 반환되는 값이 동일한 함수에 대한 호출로 계산되는 하나 이상의 경우(즉, 재귀적 호출을 사용함).
void 함수의 경우와 마찬가지로 재귀적 호출에 대한 인수는 직관적으로 "더 작아야" 한다
■ 반환되는 값이 재귀적 호출을 사용하지 않고 계산되는 하나 이상의 경우.
재귀적 호출이 없는 경우를 기저 경우 또는 정지 경우라고 한다.
이 기법은 다음 프로그래밍 예제에 나와 있다.
예: 다른 제곱 함수
3장에서는 제곱을 계산하는 사전 정의된 함수 pow를 소개했다.
예를 들어 pow(2.0, 3.0)는 2.03.0을 반환하므로 다음은 변수 결과를 8.0으로 설정한다:
double result = pow(2.0, 3.0);
함수 pow는 double형의 두 인수를 사용하고 double형의 값을 반환한다.
디스플레이 13.3은 유사하지만
double형보다는 int형으로 작동하는 함수에 대한 재귀적 정의를 포함한다.
이 새로운 함수를 power라고 한다.
예를 들어, 2^3 = 8이므로 다음은 result2의 값을 8로 설정한다:
int result2 = power(2, 3);
함수 power을 정의하는 우리의 주된 이유는 재귀 함수의 간단한 예를 가지기 위해서이지만,
함수 power이 함수 pow보다 더 나은 경우가 있다.
함수 pow은 대략적인 양에 불과한 double형의 값을 반환한다.
함수 power은 정확한 양인 int형의 값을 반환한다.
어떤 경우에는 함수 power의 거듭된 정확도가 필요할 수 있다.
함수 power의 정의는 다음 공식을 기반으로 한다:
xn = x^(n-1) * x
이 공식을 C++로 변환하면 거듭제곱으로 반환되는 값(x, n)이 된다
다음 식의 값과 같아야 한다
power(x, n - 1)*x
디스플레이 13.3에 제공된 power의 정의는 power에 대해 다음과 같은 값을 반환한다:
(x, n), provided n > 0.
n이 0과 같은 경우는 정지 경우(stopping case)이다.
n이 0이면 power (x, n) (x^0가 1이므로) 단순하게 1을 반환한다.
일부 표본 값으로 함수의 거듭제곱을 호출했을 때 어떤 일이 일어나는지 알아보겠다.
먼저 다음과 같은 간단한 표현을 고려한다:
power(2, 0)
함수를 호출하면
x = 2, n = 0으로 설정되고 함수 정의 본문의 코드가 실행된다.
n의 값은 허용값이므로 if-else 문이 실행된다.
n <= 0 이므로 다른 값 뒤의 return문이 사용되므로 함수 호출은 1을 반환한다.
따라서 다음은 result3의 값을 1로 설정한다:
result3 = power(2, 0);
디스플레이 13.3 재귀 함수 power
//Program to demonstrate the recursive function power.
#include <iostream>
#include <cstdlib>
using std::cout;
using std::endl;
int power( int x, int n);
//Precondition: n >= 0.
//Returns x to the power n.
int main( )
{
for ( int n = 0; n < 4; n++)
cout << "3 to the power " << n
<< " is " << power(3, n) << endl;
return 0;
}
//uses iostream and cstdlib:
int power( int x, int n)
{
if (n < 0)
{
cout << "Illegal argument to power.\n";
exit(1);
}
if (n > 0)
return ( power(x, n - 1) * x );
else // n == 0
return (1);
}
샘플 대화 상자
3 to the power 0 is 1
3 to the power 1 is 3
3 to the power 2 is 9
3 to the power 3 is 27
이제 재귀적 호출을 포함하는 예를 보자.
다음 식을 생각해 보자
power(2, 1)
함수를 호출하면 x = 2, n = 1로 설정하고 함수 정의 본문의 코드를 실행한다.
n > 0 이므로 반환되는 값을 결정하기 위해 다음 return문을 사용한다:
return ( power(x, n - 1) * x );
이 경우 다음과 같은 경우에 해당한다
return ( power(2, 0) * 2 );
이때 power(2, 1)의 계산이 중지되고 이 중지된 계산의 복사본이 스택에 놓여진 후
컴퓨터가 power(2, 0)의 값을 계산하기 위해 새로운 함수 호출을 시작한다.
이미 보신 바와 같이 power(2, 0)의 값은 1이다.
power(2, 0)의 값을 결정한 후
컴퓨터는 식 power(2, 0)를 자신의 값인 1로 대체하고 중지된 계산을 재개한다.
재개된 계산은 앞의 반환문에서 power(2, 1)의 최종 값을 다음과 같이 결정한다:
power (2, 0) * 2 = 1 * 2 = 2
따라서 power(2, 1)에 대해 반환되는 최종 값은 2이다.
따라서 다음은 result4의 값을 2로 설정한다:
result4 = power(2, 1);
두 번째 인수의 숫자가 클수록 재귀적 호출의 체인이 길어진다.
예를 들어, 다음 문장을 고려한다
cout << power(2, 3);
power(2, 3)의 값은 다음과 같이 계산된다:
power(2, 3)는 power(2, 2)*2
power(2, 2)는 power(2, 1)*2
power(2, 1)은 power(2, 0)*2
power(2, 0)는 1 (stopping case)
컴퓨터가 정지 경우(stopping case)가 power(2, 0)에 도달하면
3개의 일시 중지 계산이 있게 된다.
정지 경우(stopping case)에 대해 반환된 값을 계산한 후
가장 최근에 중단된 계산을 다시 시작하여 power(2, 1)의 값을 결정한다.
그 후 컴퓨터는 원래 호출인 power(2, 3)에 도달하여
연산을 완료할 때까지 각각의 값을 값으로 계산하여
다른 정지 연산을 플러그인하여 다른 일시 중지된 계산을 각각 완료한다.
전체 연산의 상세한 내용은 디스플레이 13.4에 나타나 있다.
디스플레이 13.4 재귀 함수 power(2,3) 호출식
재귀 호출 순서
1
↑
power(2, 0) *2
↑
power(2, 1) *2
↑
power(2, 2) *2
↑
power(2, 3)
여기서부터 시작
최종 값 계산 방법
1
↓
1 *2
1*2 is 2 ↓
2 *2
2*2 is 4 ↓
4 *2
4*2 is 8 ↓
8
power(2, 3) is 8
상호 재귀
지금까지의 우리의 예에서 재귀 함수는 동일한 함수를 직접 호출했다.
그러나 다른 함수를 통해 간접적으로 자신을 호출하는 재귀 함수를 가질 수도 있다.
상호 재귀(mutual recursion): 두 개 이상의 함수가 재귀적으로 서로를 호출하는 것
예시)
0과 1로 구성된 문자열이 주어졌다고 하자.
우리는 문자열에 짝수 개의 1이 있는지 확인하려고 한다.
우리의 전략은 왼쪽에서 오른쪽으로 문자열의 기호를 조사하여
지금까지 발견된 1의 수가 짝수일 때 evenNumberOfOnes 함수로,
지금까지 발견된 1의 수가 홀수일 때 evenNumberOfOnes 함수로 끝나는 것이다.
처음에 우리는 함수를 evenNumberOfOnes라고 부른다.
i) 문자열이 비어 있으면 -> 0^1은 짝수로 간주 -> true로 반환
ii) 문자열이 1로 시작 ->
1을 제거하고 선두의 1이 홀수의 1을 생성 ->
함수 OddNumberOfOnes를 호출
iii) 문자열이 0으로 시작 ->
0을 제거하고 선두의 0이 문자열을 짝수에서 홀수로 변경 X ->
evenNumberOfOnes를 다시 호출
함수 oddNumberOfOnes도 비슷한 전략을 따른다.
i) 문자열이 비어 있으면 -> false를 반환 -> 1의 수가 짝수가 아님
ii) 문자열이 1로 시작 ->
선두에 오는 1이 단지 짝수의 1로 다시 전환하게 만듦 ->
1을 제거하고 짝수NumberOfOnes 함수를 호출
iii) 문자열이 0으로 시작 ->
0을 제거하고 선두에 오는 0이 문자열을 홀수에서 짝수로 변경 X ->
함수 oddNumberOfOnes를 다시 호출
예를 들어, "10011"의 입력은 다음과 같이 계산된다.
evenNumberOfOnes("10011")
oddNumberOfOnes("0011")
oddNumberOfOnes("011")
oddNumberOfOnes("11")
evenNumberOfOnes("1")
oddNumberOfOnes("")
return false
선두 문자가 1일 때마다 짝수 개의 문자와 홀수 개의 문자 사이를 바꾼다.
문자열의 모든 문자를 검사한 후에 oddNumberOfOnes 함수에 도달함으로써,
우리는 1이 홀수 개이고 false는 재귀적인 호출의 연쇄를 통해 다시 반환된다고 결론지을 수 있다.
디스플레이 13.5에서는 상호 재귀 함수를 구현한다.
문자열의 첫 번째 문자를 "제거"하기 위해 substr 함수를 사용한다.
서브스트링의 길이에 매개변수를 포함하지 않고 시작 인덱스를 1로 지정함으로써
substr 함수는 인덱스 1부터 끝까지 문자열의 모든 것을 반환하고 인덱스 0의 문자를 건너뛴다.
이 프로그램은 반복적으로 쓰기가 쉽겠지만
여기서 제시된 아이디어를 상호 재귀를 사용하여
더 이해하고 구현하기 쉬운 정교한 파서(parser)로 확장할 수 있다.
디스플레이 13.5 문자열에 짝수 개의 1이 있는지 확인하기 위한 상호 재귀
// uses iostream and string
// If the recursive calls end in this function with an empty string
// then we had an even number of 1s.
bool evenNumberOfOnes(string s)
{
if (s.length() == 0)
return true; // Is even
else if (s[0]=='1')
return oddNumberOfOnes(s.substr(1));
else
return evenNumberOfOnes(s.substr(1));
}
// if the recursive calls ends in this function with an empty string
// then we had an odd number of 1s.
bool oddNumberOfOnes(string s)
{
if (s.length() == 0)
return false; // Not even
else if (s[0]=='1')
return evenNumberOfOnes(s.substr(1));
else
return oddNumberOfOnes(s.substr(1));
}
int main ()
{
string s = "10011";
if (evenNumberOfOnes(s))
cout << "Even number of ones." << endl;
else
cout << "Odd number of ones." << endl;
return 0;
}
샘플 대화 상자
Odd number of ones.
13.3 재귀적 사고
재귀적 설계기법
재귀 함수를 정의하고 사용할 때, 당신은 스택과 일시 중단된 계산을 계속해서 알고 싶어하지 않는다.
재귀의 힘은 당신이 그 세부 사항을 무시하고
컴퓨터가 당신을 대신해 부기(bookkeeping)를 하도록 내버려 둘 수 있다는 사실에서 비롯된다.
디스플레이 13.3의 함수 power의 예를 생각해 보자.
power의 정의를 생각하는 방법은 다음과 같다:
power(x, n)은
power(x, n - 1)*x
를 반환한다.
xn은 xn-1 *x와 같으므로,
연산이 항상 정지 사례(stopping case)에 도달하고 올바르게 계산될 것이라면,
이 값은 반환해야 할 올바른 값이다.
따라서 재귀적 정의가 올바른지 확인한 후,
재귀적 호출들의 연쇄가 항상 정지 사례(stopping case)에 도달하고
정지 사례가 항상 올바른 값을 반환하는 것만 확인하면 된다.
재귀 함수를 설계할 때는
프로그램에서 해당 함수의 인스턴스에 대한 재귀 호출의 전체 시퀀스를 추적할 필요가 없다.
값을 반환하는 함수의 기준
함수가 값을 반환하는 경우 다음 세 가지 속성이 만족되는지 확인하기만 하면 된다:
1. 무한 재귀는 없다.
(재귀적 호출은 또 다른 재귀적 호출을 초래할 수도 있고,
또 다른 재귀적 호출을 초래할 수도 있지만,
그러한 재귀적 호출의 모든 체인은 결국 중지 케이스에 도달한다.)
2. 각 정지 케이스(stopping case)는 해당 케이스에 대한 정확한 값을 반환한다.
3. 재귀와 관련된 경우: 모든 재귀 호출이 올바른 값을 반환하면 함수에 의해 반환되는 최종 값이 올바른 값이 된다.
예를 들어, 디스플레이 13.3의 함수 전력을 생각해 보자.
1. 무한 재귀는 없다.
power(x,n)에 대한 두 번째 인수는 재귀 호출마다 1씩 감소하므로
재귀 호출 연쇄는 결국 중단 사례인 대소문자 power(x, 0)에 도달해야 한다.
따라서 무한 재귀는 없다.
2. 각 정지 케이스는 그 경우에 대한 정확한 값을 반환한다.
유일한 정지 케이스는 power(x, 0)이다.
power(x, 0) 형태의 호출은 항상 1을 반환하며,
x0에 대한 정확한 값은 1이다.
따라서 정지 케이스는 정확한 값을 반환한다.
3. 재귀와 관련된 경우,
모든 재귀 호출이 올바른 값을 반환하면
함수에 의해 반환되는 최종 값이 올바른 값이다.
재귀와 관련된 경우는 n > 1일 때뿐이다.
n > 1일 때 power(x, n)는 power(x, n - 1) * x를 반환한다.
이 값이 올바른 반환 값인지 확인하려면
power(x, n - 1)가 올바른 값을 반환하면
power(x, n - 1)가 x^(n-1)을 반환하고 power(x, n)가 x^n인 x^(n-1) * x를 반환한다.
그리고 이 값이 power(x, n)에 대한 올바른 값이다.
이것이 거듭제곱의 정의가 정확한지 확인하기 위해 필요한 것이다.
(앞의 기술을 수학적 귀납법(mathematical induction)이라고 하는 개념이다.)
우리는 값을 반환하는 재귀적 함수의 정확성을 검사하는 데 사용할 세 가지 기준을 제시했다.
재귀적 void 함수의 기준
기본적으로 재귀적 void 함수에도 동일한 규칙이 적용될 수 있다.
재귀적 void 함수의 정의가 다음 세 가지 기준을 만족한다는 것을 보여주면
void 함수가 올바르게 수행된다는 것을 알 수 있다:
1. 무한 반복은 없다.
2. 각 정지 케이스(stopping case)는 해당 케이스에 대해 올바른 동작을 수행한다.
3. 재귀와 관련된 각 케이스에 대해 모든 재귀 호출이 올바르게 수행되면 전체 케이스가 올바르게 수행된다.
이진 탐색(binary search)
이 절에서는 배열에 지정된 값이 포함되어 있는지 확인하기 위해 배열을 검색하는 재귀 함수를 개발한다.
예를 들어, 배열은 더 이상 유효하지 않은 신용 카드의 숫자 목록을 포함할 수 있다.
상점 점원은 고객의 카드가 유효한지 또는 유효하지 않은지 목록을 검색해야 한다.
배열 a의 인덱스는 정수 0부터 finalIndex이다.
배열을 쉽게 검색하기 위해 배열이 정렬되었다고 가정하겠다.
따라서 다음을 알 수 있다:
a[0] ≤ a[1] ≤ a[2] ≤ ... ≤ a[finalIndex]
배열을 검색할 때는 값이 목록에 있는지 없는지, 값이 있으면 목록의 위치를 알고 싶을 것이다.
예를 들어, 신용카드 번호를 검색할 때 배열 인덱스는 기록 번호로 사용될 수 있다.
동일한 인덱스로 인덱싱된 다른 배열에는 의심스러운 카드를 보고하는 데 사용할 전화 번호나 기타 정보가 저장될 수 있다.
따라서 원하는 값이 배열에 있으면 배열의 위치를 함수가 알려주기를 원한다.
이제 이 문제를 풀기 위한 알고리즘을 만들어 보자.
매우 구체적인 방법으로 문제를 시각화하는 데 도움이 될 것이다.
숫자 목록이 너무 길어서 책으로 다 나열하는 데 시간이 걸린다고 가정해 보자.
이것은 사실 유효하지 않은 신용카드 번호가 컴퓨터를 사용할 수 없는 상점들에게 어떻게 분배되는지를 보여준다.
만약 당신이 점원인데 신용카드를 건네받았다면, 당신은 그것이 목록에 있는지 확인해야 하므로 유효하지 않다.
어떻게 진행할까? 책을 가운데로 열고 숫자가 있는지 확인하자.
알고리즘의 첫 번째 초안
만약 그렇지 않고 숫자가 가운데 숫자보다 작다면, 책의 처음 부분을 향해 뒤로 이동하라.
숫자가 가운데 숫자보다 크다면, 책의 끝 부분을 향해 당신의 길로 이동하라.
found = false; //so far.
mid = approximate midpoint between 0 and finalIndex;
if (key == a[mid])
{
found = true;
location = mid;
}
else if (key < a[mid])
search a[0] through a[mid - 1];
else if (key > a[mid])
search a[mid + 1] through a[finalIndex];
더 짧은 목록을 검색하는 것은 우리가 수행할 알고리즘을 설계하는 바로 그 작업의 작은 버전이기 때문에,
이 알고리즘은 자연스럽게 재귀를 사용하는 데 도움이 된다.
더 작은 목록은 알고리즘 자체에 대한 재귀 호출로 검색할 수 있다.
우리의 의사 코드는 C++ 코드로 쉽게 번역하기에는 조금 부정확하다.
문제는 재귀적 호출과 관련이 있다. 다음 두 가지 재귀적 호출이 표시된다:
search a[0] through a[mid - 1];
그리고.
search a[mid + 1] through a[finalIndex];
이러한 재귀적 호출을 구현하기 위해서는 두 개의 매개변수가 더 필요하다.
재귀적 호출은 배열의 하위 범위를 검색할 것임을 지정한다.
어떤 경우에는 0부터 중간 - 1까지 인덱싱된 요소이다.
다른 경우에는 finalIndex까지 + 1까지 인덱싱된 요소이다.
두 개의 추가 매개변수는 검색의 첫 번째 인덱스와 마지막 인덱스를 지정하므로
처음과 마지막 인덱스를 호출한다.
알고리즘의 첫 번째 수정 버전
0과 finalIndex 대신 가장 낮은 인덱스와 가장 높은 인덱스에 대해
이러한 매개변수를 사용하여 의사 코드를 더 정확하게 표현하면 다음과 같다:
To search a[first] through a[last] do the following:
found = false; //so far.
mid = approximate midpoint between first and last;
if (key == a[mid])
{
found = true;
location = mid;
}
else if (key < a[mid])
search a[first] through a[mid - 1];
else if (key > a[mid])
search a[mid + 1] through a[last];
전체 배열을 검색하기 위해 알고리즘은 첫 번째 집합을 0으로 설정하고 마지막 집합을 finalIndex로 설정한다.
재귀적 호출은 처음과 마지막에 다른 값을 사용한다.
예를 들어 첫 번째 재귀적 호출은 처음에는 0으로 설정하고 마지막에는 계산된 값 중간 - 1로 설정한다.
중지 케이스(stopping case)
여느 재귀적 알고리즘과 마찬가지로 우리는 무한 재귀를 생성하는 대신 알고리즘이 종료되도록 해야 한다.
만약 목록에서 찾고자 하는 번호가 발견되면 재귀적 호출이 없고 프로세스가 종료되지만,
우리는 그 번호가 목록에 없을 때를 탐지할 수 있는 방법이 필요하다.
재귀적 호출마다 첫 번째 값이 증가하거나 마지막 값이 감소한다.
알고리즘 마지막 버전
만약 그들이 서로 지나가다가 처음에 마지막보다 더 커지면,
우리는 더 이상 확인할 인덱스가 남아 있지 않고 숫자 키가 배열에 없다는 것을 알게 될 것이다.
이 테스트를 의사코드에 추가하면 그림 13.6과 같은 완전한 해를 얻을 수 있다.
코딩
이제 우리는 의사 코드를 일상적으로 C++ 코드로 변환할 수 있다.
그 결과는 디스플레이 13.7에 나타나 있다.
함수 search는 디스플레이 13.6에 주어진 재귀적 알고리즘을 구현한 것이다.
함수가 샘플 배열에서 어떻게 수행되는지에 대한 도표는 디스플레이 13.8에 나와 있다.
함수 search는 원래 작업보다 더 일반적인 문제를 해결한다는 것을 주목하자.
우리의 목표는 전체 배열을 검색하는 함수를 설계하는 것이었지만,
함수 search는 처음과 마지막에 인덱스 경계를 지정하여 배열의 모든 간격을 검색할 수 있게 해준다.
이것은 재귀 함수를 설계할 때 흔히 볼 수 있는 일이다.
재귀 알고리즘을 표현하기 위해서는 더 일반적인 문제를 해결해야 하는 경우가 많다.
이 경우 처음과 마지막이 0과 finalIndex로 같은 값으로 설정되어 있는 경우에만 답을 구하고자 했다.
그러나 재귀 호출은 0과 finalIndex가 아닌 다른 값으로 설정할 것이다.
디스플레이 13.6 이진 탐색을 위한 의사 코드
int a[ Some_Size_Value];
Algorithm to Search a[first] through a[last]
//Precondition:
//a[first]<= a[first + 1] <= a[first + 2] <=... <= a[last]
To locate the value key:
if (first > last) //A stopping case
found = false;
else
{
mid = approximate midpoint between first and last;
if (key == a[mid]) //A stopping case
{
found = false;
location = mid;
}
else if key < a[mid] //A case with recursion
search a[first] through a[mid - 1];
else if key > a[mid] //A case with recursion
search a[mid + 1] through a[last];
}
디스플레이 13.7 이진 탐색을 위한 재귀 함수
//Program to demonstrate the recursive function for binary search.
#include <iostream>
using std::cin;
using std::cout;
using std::endl;
const int ARRAY_SIZE = 10;
void search( const int a[ ], int first, int last,
int key, bool& found, int& location);
//Precondition: a[first] through a[last] are sorted in increasing
//order.
//Postcondition: if key is not one of the values a[first] through
//a[last], then found == false; otherwise, a[location] == key
//and found == true.
int main( )
{
int a[ARRAY_SIZE];
const int finalIndex = ARRAY_SIZE - 1;
int key, location;
bool found;
cout << "Enter number to be located: ";
cin >> key;
search(a, 0, finalIndex, key, found, location);
if (found)
cout << key << " is in index location "
<< location << endl;
else
cout << key << " is not in the array." << endl;
return 0;
}
void search( const int a[ ], int first, int last,
int key, bool& found, int& location)
{
int mid;
if (first > last)
{
found = false;
}
else
{
mid = (first + last)/2;
if (key == a[mid])
{
found = true;
location = mid;
}
else if (key > a[mid])
{
search(a, first, mid - 1, key, found, location);
}
else if (key > a[mid])
{
search(a, mid + 1, last, key, found, location);
}
}
}프로그램의 이 부분에는 배열 a를 채우고 정렬하기 위한 코드가 포함되어 있다.
정확한 세부 정보는 이 예제와 무관하다.
디스플레이 13.8 함수 검색 실행
key is 63
| a[0] | 15 | first == 0 |
| a[1] | 20 | |
| a[2] | 35 | |
| a[3] | 41 | |
| a[4] | 57 | mid = (0 + 9)/2 |
| a[5] | 63 | |
| a[6] | 75 | |
| a[7] | 80 | |
| a[8] | 85 | |
| a[9] | 90 | last == 9 |
↓
| a[0] | 15 | |
| a[1] | 20 | |
| a[2] | 35 | Not in this half |
| a[3] | 41 | |
| a[4] | 57 | |
| a[5] | 63 | first == 5 |
| a[6] | 75 | |
| a[7] | 80 | mid = (5 + 9)/2 |
| a[8] | 85 | |
| a[9] | 90 | last == 9 |
↓
| a[0] | 15 | |
| a[1] | 20 | |
| a[2] | 35 | |
| a[3] | 41 | |
| a[4] | 57 | |
| a[5] | 63 | first == 5 |
| a[6] | 75 | last == 6 |
| a[7] | 80 | Not here |
| a[8] | 85 | |
| a[9] | 90 | Not here |
mid = (5 + 6)/2 which is 5
a[mid] is a[5] == 63
found = TRUE;
location = mid;
재귀 확인하기
재귀적 디자인 기법이라는 제목의 서브섹션에서는
재귀적 void 함수의 정의가 올바른지 확인하기 위해 확인해야 할 세 가지 기준을 제시했다.
디스플레이 13.7의 함수 search를 위해 이 세 가지를 확인해 보겠다.
1. 무한 재귀는 없다.
각각의 재귀적 호출에서 첫 번째 값이 증가하거나 마지막 값이 감소한다.
재귀적 호출들의 연쇄가 다른 방식으로 끝나지 않는다면,
결국 함수는 마지막보다 더 큰 첫 번째 값으로 호출될 것이고,
이것은 정지 케이스이다.
2. 각 정지 케이스는 해당 케이스에 대해 올바른 동작을 수행한다.
first > last일 때와 key == a[mid]일 때 두 개의 정지 케이스가 있다.
각 케이스를 고려해 보겠다.
first > last이면 a[first]와 a[last] 사이에 배열 요소가 없으므로
key는 배열의 이 세그먼트에 없다.
(배열의 이 세그먼트에는 아무것도 없다!)
따라서 first > last인 경우 함수 검색은 false로 올바르게 설정한다.
key == a[mid]이면 알고리즘은 false로 설정하고 false로 설정한다.
따라서 두 중지 경우 모두 정확하다.
3. 재귀와 관련된 각 경우에 대해 모든 재귀 호출이 올바르게 수행되면 전체 경우가 올바르게 수행된다.
재귀 호출이 있는 경우는 key < a[mid]일 때와 key > a[mid]일 때 두 가지이다.
다음을 수행해야 한다
이 두 가지 경우를 각각 확인한다.
case 1) key < a[mid]라고 가정한다.
이 경우 배열이 정렬되므로 key가 배열 내의 임의의 위치에 있다면
key는 a[first]부터 a[mid-1]까지의 원소 중 하나임을 알 수 있다.
따라서 함수는 이 원소들을 검색하기만 하면 되고, 이것은 재귀적 호출과 정확히 일치하다
search(a, first, mid - 1, key, found, location);
재귀 호출이 맞다면, 전체 동작이 맞다.
case 2) key > a[mid]라고 가정한다.
이 경우, 배열이 정렬되므로, 만약 key가 배열의 어느 곳에 있다면,
key는 a[mid + 1]부터 a[last]까지의 원소들 중 하나임을 알 수 있다.
따라서 함수는 이 원소들을 검색하기만 하면 되고, 이것은 재귀적인 호출과 정확히 일치하다
search(a, mid + 1, last, key, found, location);
따라서 재귀적 호출이 정확하다면 전체 동작이 정확하다.
따라서 두 경우 모두 함수는 올바른 동작을 수행한다
(재귀적 호출이 올바른 동작을 수행한다고 가정할 때).
함수 search는 우리의 세 가지 테스트를 모두 통과하므로 좋은 재귀 함수 정의이다.
효율성
이진 탐색 알고리즘(binary search algorithm)은
단순히 모든 배열 요소를 순서대로 시도하는 알고리즘에 비하면 매우 빠르다.
이진 탐색에서는 처음에 배열의 절반 정도를 제거한다.
그런 다음에 배열의 4분의 1, 그다음에 8분의 1 정도를 제거한다.
이렇게 절약한 양을 합하면 엄청나게 빠른 알고리즘이 된다.
원소가 100개인 배열에서 이진 탐색은 배열 요소를 키와 7개 이상 비교할 필요가 없다.
간단한 직렬 탐색은 배열 요소를 키와 비교할 수 있으며,
평균적으로 약 50개의 배열 요소를 키와 비교할 것이다.
더구나 배열이 클수록 절감 효과는 극적일 것이다.
원소가 1000개인 배열에서 이진 탐색은 배열 원소 10개 정도를 키 값과 비교하기만 하면 되고,
단순 직렬 탐색 알고리즘은 평균 500개 정도이다.
함수 search의 반복 버전은 디스플레이 13.9에 제공된다.
어떤 시스템에서는 반복 버전이 재귀 버전보다 더 효율적으로 실행될 것이다.
반복 버전에 대한 알고리즘은 재귀 버전을 미러링하여 유도되었다.
반복 버전에서는 로컬 변수가 재귀 버전에서 매개 변수의 역할을 first과 last로 반영하며,
매개 변수의 이름도 first과 last로 지정된다.
이 예에서 알 수 있듯이 나중에 재귀 알고리즘을 반복 알고리즘으로 변환할 것으로 예상하더라도
재귀 알고리즘을 도출하는 것이 합리적인 경우가 많다.
디스플레이 13.9 이진 탐색의 반복 버전
Function Declaration
void search( const int a[ ], int lowEnd, int highEnd,
int key, bool& found, int& location);
//Precondition: a[lowEnd] through a[highEnd] are sorted in
//increasing order.
//Postcondition: If key is not one of the values a[lowEnd]
//through a[highEnd], then found == false; otherwise,
//a[location] == key andfound == true.
Function Definition
void search( const int a[ ], int lowEnd , int highEnd,
int key, bool& found, int& location)
{
int first = lowEnd;
int last = highEnd;
int mid;
found = false; //so far
while ((first <= last) && !(found))
{
mid = (first + last)/2;
if (key == a[mid])
{
found = true;
location = mid;
}
else if (key < a[mid])
{
last = mid - 1;
}
else if (key > a[mid])
{
first = mid + 1;
}
}
}
'프로그래밍 공부 > OOP' 카테고리의 다른 글
| 15장 다형성과 가상함수 (1) | 2023.11.30 |
|---|---|
| 14장 상속 (0) | 2023.11.29 |
| 12장 스트림 및 파일 입출력 (1) | 2023.11.27 |
| 11장 분할 컴파일 및 네임스페이스 (1) | 2023.11.26 |
| 10장 포인터와 동적 배열 (1) | 2023.11.26 |