CH 07 Programming with Recursion
Recursive Call
Recursion
- 호출하는 주체와 호출하는 객체가 서로 같은 것
- Direct Recursion: 함수 f에서 함수 f 직접 호출
- Indirect Recursion: 함수 f에서 실행되는 함수 g에서 함수 f 간접 호출
- Recursive Call과 Loop는 서로 호환 가능하다
- Recursive Call은 iterative solution보다 비효율적인 해결 방식
- Recursive Call을 쓰면 코드가 깔끔하고 이해하기 쉬움
Some Definition
- Base Case: Recursion을 쓰면 빠져나오는 경우
- General Case: Recursion을 실행하는 경우
- Recursive Algorithm: Base Case + General Case
- 다루고자 하는 instance들이 base case를 향해 가야 함
- Recursion 호출과 반대 방향으로 값 return
Example
Factorial
- Base Case: 1!
- General Case: n! = n * (n-1)!
- Factorial Function
int Factorial(int num) {
if (num == 1)
return 1;
else
return Factorial(num - 1);
}Combination
- Base Case
- Combination(n, 1) = n
- Combination(n, n) = 1
- General Case: Combination (c, k) = Combination(n-1, k) + Combination(n-1, k-1)
- Combination Function
int Combination(int n, int k) {
if (k == 1)
return n;
else if (k == n)
return 1;
else
return Combination(n-1, k) + Combination(k-1, n-1);
}ValueInList
- 배열 안에 value 값이 있는지 search 하는 함수
- Base Case: value 값을 찾은 경우, 배열을 다 찾아도 없는 경우
- General Case: n! = value 값을 못 찾은 경우 startIndex 뒤에만 검색
- ValueInList Function
bool ValueInList(ListType list, int value, int startIndex) {
if(list->info[startIndex] == value)
return true;
else if (startIndex == list.length - 1)
return false;
else
return ValueInList(list, startIndex - 1);
}RevPrint
- list의 끝 요소부터 출력하는 함수
- Base Case: listPtr == NULL
- General Case: listPtr != NULL
- Factorial Function
int RevPrint(NodeType* listPtr) {
if(listPrt != NULL):
RevPrint(listPtr->next);
std::cout << listPtr->info << std::endl;
}BinarySearch
- Base Case: start > end 거나 item을 찾았을 때
- General Case: start < end 이고 item을 찾지 못했을 때
- BinarySearch Function
bool BinarySearch(int info[], int item, int start, int end) {
int mid = (start + end) / 2;
if (start > end)
return false;
else if (info[mid] == item)
return true;
else {
if (info[mid] > item)
BinarySearch(info, item, start, mid - 1);
else
BinarySearch(info, item, mid + 1, end);
}
}Runtime Stack Activation Record
Function Call
- 프로그램이 실행되면 위에서부터 한 줄씩 코드 실행
void h() {
f();
}
void g() {
f();
}- f()가 return된 후 h() 다음으로 가야 하는지 g() 다음으로 가야 하는지 기계는 알 수 없음
- 따라서 function call을 할 때 어디로 돌아와야 하는지 return address 같이 전송
Stack Activation Frame
- 함수 call과 return을 stack으로 관리
- f 호출 후 g를 호출하면
| call f | call g |
|---|---|
| g() | |
| f() | f() |
- Stack에 저장되는 각각 함수의 크기는 local variable 수에 따라 달라질 수 있음
- 함수의 일이 끝나면 Stack point가 내려와야 하는데 함수마다 정의한 크기가 다르기 때문에 얼마나 내려와야 하는지 정보 저장
- 함수 call = activation record instance를 stack에 push
Activation Record Instance
- 실제 함수를 호출했을 때 stack에 push되는 item의 instance
- 구성
- Return Address: 함수를 호출하는 line
- Parameter
- Local variable
- Return value
function Activation Record Inastance Return value f() Local variable Parameter Return Addreaa
- Recursive를 실행할 때마다 함수를 call하기 때문에 Activation record instance 생성
- Recursive call이 비효율적인 이유
Direction of Recursion
Tail Recursion
- 함수의 가장 마지막에서 recursion이 일어나는 구조
- loop로 쉽게 변환 가능
- Example: ValueInList function
bool ValueInList(ListType list, int value, int startIndex) {
if(list->info[startIndex] == value)
return true;
else if (startIndex == list.length - 1)
return false;
else
return ValueInList(list, startIndex - 1);
}- Invert iteration version
bool ValueInList(ListType list, int value, int startIndex) {
bool found = false;
while (!found) {
if (list->info[startIndex] == value)
found = true;
else
startIndex++;
return found;
}
}Reverse Recursion
- Recursion이 행동 이전에 실행되는 경우
- Iteration으로 바꾸기 위해서는 stack 필요
- Example: RevPrint function
int RevPrint(NodeType* listPtr) {
if(listPrt != NULL):
RevPrint(listPtr->next);
std::cout << listPtr->info << std::endl;
}- Invert Iteratoin version
int RevPrint(NodeType* listPtr) {
StackType<ItemType> stack;
listPtr = listData;
while (listPtr != NULL) {
stack.push(listPtr->info);
listPtr = listPtr->next;
}
while (!stack.IsEmpty()) {
std::cout << stack.top() << std::endl;
stack.pop();
}
}Additional Algorithm
Quick Sort Algorithm
- 큰 문제를 나눠서 해결하는 devided conquar 방식
- splitVal을 기준으로 작은 item은 앞으로, 큰 item은 뒤로 위치 이동
- Recursive QuickSort Function
int Split(int values[], int first, int last) {
int pivot, temp;
int low, high;
low = first + 1;
high = last;
pivot = values[first];
while (low < high) {
while (low <= last && values[low] < pivot)
low++;
while (high >= first && values[high] > pivot)
high--;
if (low < high) {
temp = values[low];
values[low] = values[high];
values[high] = temp;
}
}
temp = values[first];
values[first] = values[high];
values[high] = temp;
return high;
}
void QuickSort(int values[], int first, int last) {
if (first < last) {
int splitPoint = Split(values, first, last);
QuickSort(values, first, splitPoint - 1);
QuickSord(values, splitPoint + 1, last);
}
}Sorted List InserItem
- Base Case
- new item이 첫 item일 때
- new item이 제일 작아서 가장 앞에 들어가야 할 때
- 넣을 위치를 찾았을 때
- General Case: Insert(locaion->next, item)
- InsertItem function
template<class ItemType>
void Insert(NodeType<ItemType>* location, ItemType item) {
if ((location == NULL) || (item < location->info) {
NodeType<ItemType>* temp = location;
location = new NodeType<ItemType>;
location->info = item;
location->next = temp;
}
else
Insert(locaion->next, item);
}
template<class ItemType>
void SortedType::InsertItem(ItemType item) {
Insert(listData, item);
}Sorted List DeleteItem
- Base Case: 지울 애를 찾았을 때
- General Case: Delete(location->next, item)
- DeleteItem function
template<class ItemType>
void Delete(NodeType<ItemType>* location, ItemType item) {
if (location->info == item) {
NodeType<ItemType>* temp = locaion;
location = location->next;
delete temp;
}
else
Delete(location->next, item);
}
template<class ItemType>
void SortedType::DeleteItem(ItemType item) {
Delete(listData, item);
}LAB
Fibonacci
- 피보나치 수열(Fibonacci sequence)은 다음과 같은 정수의 연속
- 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 …
- 이 정수의 연속은 현 시점에서 이전의 두 수에 대한 합
- Base Case: Fib(0) = 0
- General Case: Fib(N) = Fib(N-2)+Fib(N-1)
- Recursive version
int Fibonacci(int n) {
if (n == 0 || n == 1)
return n;
else
return Fibonacci(n - 2) + Fibonacci(n - 1);
}- Iteration version
int Fibonacci(int n) {
if (n == 0 || n == 1)
return n;
int result;
int num1 = 0;
int num2 = 1;
for (int i = 1; i < n; i++) {
result = num1 + num2;
num1 = num2;
num2 = result;
}
return result;
}SqurRoot
- 다음은 주어진 근사치 답(approx)과 지정된 허용치(tol) 내의 수에 대한 제곱근 근사치를 계산하는 함수
- number: 제곱근을 구하고자 하는 수
- approx: 제곱근의 근사치
- tol: 제곱근에 얼마만큼 근사해야 하는지에 대한 범위
- Recursion version
#include <iostream>
#include <cmath>
using namespace std;
float SqrRoot(float number, float approx, float tol) {
if (fabs(approx * approx - number) <= tol)
return approx;
else
return SqrRoot(number, (approx * approx + number) / (2 * approx), tol);
}- Iteration version
#include <iostream>
#include <cmath>
using namespace std;
float SqrRoot(float number, float approx, float tol) {
while (fabs(approx * approx - number) > tol) {
approx = (approx * approx + number) / (2 * approx);
}
return approx;
}NumPath
- 어진 N*N 이차원 격자 내에서 (1,1)을 시작으로 (N,N)까지 이동 가능한 경로의 수를 계산
- 단 위 방향, 우측 방향으로만 한 칸씩 이동 가능
- (r,c) 에서 한칸만 움직인다면 경우의 수는 오른쪽 이동과 위쪽 이동 두 가지만 존재
- 따라서 , (r,c)부터 (n,n)까지 가는 경로의 수는 (r+1,c)부터 (n,n)까지 가는 (r, c+1)부터 (n,n)까지 가는 경우의 수의 합
- 현재 위치의 r 또는 c가 n인 경우는 base case로서 경로의
수는 1 - (1,1)에서 (n,n)까지 이동 가능한 경로를 계산하는 NumPaths 함수를 구현
#include <iostream>
using namespace std;
int NumPaths(int row, int col, int n) {
if ((row == n) || (col == n))
return 1;
else
return NumPaths(row + 1, col, n) + NumPaths(row, col + 1, n);
}- A에서 구현한 방법은 같은 칸에서 n,n까지의 경로를 재계산 하는 경우가 발생하기 때문에 2차원 행렬을 이용하여 재계산하지 않도록 알고리즘을 수정
#include <iostream>
using namespace std;
int NumPaths(int row, int col, int n) {
if ((row == n) || (col == n))
return 1;
else
return NumPaths(row + 1, col, n) + NumPaths(row, col + 1, n);
}
#define MAXROWS 50
#define MAXCOLS 50
int mat[MAXROWS][MAXCOLS];
int NumPathsMatrix(int row, int col, int n) {
if (mat[row][col] == -1) {
if (row == col) {
mat[row][col] = 0;
return 0;
}
else if ((row == n) || (col == n)) {
mat[row][col] = 1;
return 1;
}
else {
mat[row][col] = NumPaths(row + 1, col, n) + NumPaths(row, col + 1, n);
return mat[row][col];
}
}
}MinLoc
- 다음의 두 재귀 루틴이 갖는 인자는 중복되지 않고 정렬되지 않는 숫자로 구성된 단일 연결 리스트에 대한 포인터
- 리스트의 각 노드는 info(숫자)와 next(다음 노드에 대한 포인터) 멤버로 구성
- 가장 최소값을 갖는 노드를 리턴하는 멤버함수 MinLoc을 구현
#include <iostream>
#include <new>
using namespace std;
template<class ItemType>
NodeType<ItemType>* UnsortedType<ItemType>::MinLoc(NodeType<ItemType>* location) {
if (location == NULL)
return NULL;
else if (location->next == NULL)
return location;
else {
NodeType<ItemType>* minPtr = MinLoc(location->next);
if (location->info < minPtr->info)
minPtr = location;
return minPtr;
}
}- 원소들을 정렬하기 위한 멤버함수 Sort를 구현
#include <iostream>
#include <new>
using namespace std;
template<class ItemType>
NodeType<ItemType>* UnsortedType<ItemType>::Sort(NodeType<ItemType>* location) {
NodeType<ItemType>* min;
ItemType temp;
if (location != NULL) {
min = MinLoc(location, location);
temp = min->info;
min->info = location->info;
location->info = temp;
Sort(location->next)
}
}PP
Binary Search
- 출력 예제
13 is not in the list
20 is in the list - BinarySearch
def binary_search(info, item, fromLocation, toLocation):
if fromLocation > toLocation:
return False
else:
midPoint = int((fromLocation + toLocation) / 2)
if item < info[midPoint]:
return binary_search(info, item, fromLocation, midPoint-1)
elif item == info[midPoint]:
return True
else:
return binary_search(info, item, midPoint+1, toLocation)- test
from BinSearch import *
if __name__ == '__main__':
arr = [1,3, 5, 6, 7, 10, 17, 20]
item = 13
if binary_search(arr, item, 0, len(arr) - 1) == True:
print(f'{item} is in the list.')
else:
print(f'{item} is not in the list.')
item = 20
if binary_search(arr, item, 0, len(arr) - 1) == True:
print(f'{item} is in the list.')
else:
print(f'{item} is not in the list.') Combination
- 출력 예제
C(10, 3): 120
C(5, 1): 5
C(45, 6): 8145060 - Combination
def combinations(group, members):
if(members == 1):
return group
elif (members == group):
return 1
else:
return(combinations(group-1, members-1) + combinations(group-1, members))- test
from ComBin import *
if __name__ == '__main__':
print(f"C(10,3) : {combinations(10, 3)}")
print(f"C(5,1) : {combinations(5, 1)}")
print(f"C(45,6) : {combinations(45, 6)}")Factorial
- 출력 예제
7! : 120
17! : 355687428096000
50! : 30414093201713378043612608166064768844377641568960512000000000000 - Factorial
def factorial(number):
if (number == 1):
return 1
else:
return number*factorial(number-1)- test
from Factorial import *
if __name__ == '__main__':
print(f'7! : {factorial(5)}')
print(f'17! : {factorial(17)}')
print(f'50! : {factorial(50)}')QuickSort
- 출력 예제
Before
[9, 8, 7, 6, 5, 4, 3, 2, 1]
After
[1, 2, 3, 4, 5, 6, 7, 8, 9]
Before
[1, 8, 5, 7, 3, 2, 6, 4, 9]
After
[1, 2, 3, 4, 5, 6, 7, 8, 9] - QuickSort
def split(values, first, last):
splitvalue = values[first]
saveFirst = first
onCorrectside = True
first += 1
while(first <= last):
while(onCorrectside):
if(values[first]>splitvalue):
onCorrectside = False
else:
first += 1
onCorrectside = (first <= last)
onCorrectside = (first <= last)
while(onCorrectside):
if(values[last] < splitvalue):
onCorrectside = False
else:
last -= 1
onCorrectside = (first <= last)
if(first <= last):
values[first], values[last] = values[last], values[first]
first += 1
last -= 1
splitPoint = last
values[saveFirst], values[splitPoint] = values[splitPoint], values[saveFirst]
return splitPoint
def quick_sort(values, first, last):
if(first < last):
splitPoint = split(values, first, last)
quick_sort(values, first,splitPoint-1 )
quick_sort(values, splitPoint+1, last)
return values- test
from QuickSort1 import *
if __name__ == '__main__':
arr01 = [9, 8, 7, 6, 5, 4, 3, 2, 1]
arr02 = [1, 8, 5, 7, 3, 2, 6, 4, 9]
print("Before")
print(arr01)
print("After")
print(quick_sort(arr01, 0, len(arr01) - 1))
print("\nBefore")
print(arr02)
print("After")
print(quick_sort(arr02, 0, len(arr02) - 1))Author And Source
이 문제에 관하여(CH 07 Programming with Recursion), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@morion002/CH-07-Programming-with-Recursion저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
좋은 웹페이지 즐겨찾기
