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;
}

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));
}

#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값을 제공
    }
}

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 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)까지 갈 자식 노드를 생성하는 것
}

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)까지 갈 자식 노드를 만드는 것 
}