ch7_RECURSIVE_CODE
- 피보나치 수열(기본 재귀 활용)
int Fibonacci_recursive(int n) {
if (n == 0) {
return 0;
}
else {
return n + Fibonacci_recursive(n - 1);
}
}
int Fibonacci_non_recursive(int n) {
int sum = 0;
while (n != 0) {
sum += n;
n--;
}
return sum;
}
- 조합(Combination)
int Combinations(int n, int k)
{
if(k == 1) //base case1
return n;
else if(n == k) //base case2
return 1;
else
return (Combinations(n-1,k)+ Combinations(n-1.k-1));
}
- 지수 승
int Power(int x, int n)
{
if (n==0)
return 1;
else
return (x * Power(x, n-1));
}
- 재귀를 사용한 거꾸로 출력(RevPrint)
- 재귀호출이 아니었다면 반복문을 통해 매번 끝까지 갔다가, 끝 전까지 갔다가...이거를 반복해야함
#include <iostream>
template <class ItemType>
struct NodeType
{
int info;
NodeType<ItemType>* next;
};
template <class ItemType>
void RevPrint(NodeType<ItemType>* listPtr)
{
using namespace std;
//if(listPtr==NULL) return
//Base case : if the list is empty
if (listPtr != NULL) //general case
{
RevPrint(listPtr->next); //먼저 자식을 호출(일단 끝까지 가야 하니까)
cout << listPtr->info << endl; //맨 뒤에서부터 출력->leaf의 자식부터 부모까지 거슬러 오름.
//부모에게 return값을 제공
}
}
- 재귀를 활용한 BinarySearch
template<class ItemType>
bool BinarySearch (ItemType info[], ItemType item,
int fromLocation, int toLocation)
{
if (fromLocation > toLocation) // Base case 1 first가 last가 역전된다면 이는 탐색대상이 없음.
return false;
else
{
int midPoint = (fromLocation + toLocation) / 2;
if (item < info[midPoint])
return BinarySearch(info, item, fromLocation, midPoint-1);
//왜 -1을 하였을까? mid값과 대소비교를 했을 때 제한하는 것이므로, mid값보다 왼쪽값으로 제한함.
// first <= mid <= last가 항상 성립이 되어 역전 현상이 발생하지 않는다!
else if (item == info[midPoint])
return true;
else //(item > info[midPoint])
return BinarySearch(info, item, midPoint + 1, toLocation);
}
}
- Recursive InsertItem
// recursive insertion of item into a linked list
//값을 바꾸기 위해선 location을 !!!!!reference타입으로 전달받아!!! 값을 바꿀 수 있도록 해준다.
template<class ItemType>
void Insert(NodeType<ItemType>*& location, ItemType item)
{
if (location == NULL || item < location->info) //base case- 삽입할 자리 찾음.
//처음으로 내가 작아지는 자리
{
// Save current pointer.
NodeType<ItemType>* tempPtr = location;
// Get a new node. 연결
location = new NodeType<ItemType>;
location >info = item;
location->next = tempPtr; //reference타입
}
else Insert(location->next, item); //아직 삽입할 위치 찾지 못함. 재귀를 통해 이동만 하자
//즉 leaf(base case)까지 갈 자식 노드를 생성하는 것
}
- Recursive DeleteItem
template<class ItemType>
void Delete(NodeType<ItemType>*& listPtr, ItemType item)
{
if (item == listPtr->info) //basecase - 자리 찾음
{
NodeType<ItemType>* tempPtr = listPtr;//tempPtr이 가리키는 것을 listPtr도 똑같이 가리킴
listPtr = listPtr->next;
delete tempPtr; //해제
}
else
Delete(listPtr->next, item); //general case- 자리 찾지 못했으므로 이동
//즉 재귀를 통해 leaf(base case)까지 갈 자식 노드를 만드는 것
}
Author And Source
이 문제에 관하여(ch7_RECURSIVE_CODE), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jjeong/ch7RECURSIVECODE저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)