// recursion examples:
// to compile: g++ -std=c++11 recursion.cpp
//

#include <iostream>
#include <vector>
#include <string.h>

using namespace std;

template <class iterator>
typename iterator_traits<iterator>::value_type sum(iterator beg, iterator end) 
{
        if (beg == end) return 0;
        return *beg + sum(++beg, end); 
}


template <class iterator, class val>
bool mysearch(iterator beg, iterator end, val v) 
{
        if (beg == end) return false;
        if (*beg == v) return true;
        else return mysearch(++beg, end, v); 
}

template<class T>
void insertion_sort(vector<T>& v, int b, int e)
{
        if (b >=e) return;
        insertion_sort(v, b+1, e);

	T t = v[b];
        int j = b+1;
        while ((t > v[j]) && (j <= e)) {v[j-1] = v[j]; j++;}
        v[j-1] = t;
}

int main( )
{
        vector<int> test{1, 2, 3, 4, 5, 100, 20, 5};
        vector<double> test1{1.0, 2.5, 3.0};

        cout << sum(test.begin(), test.end()) << endl;
        cout << sum(test1.begin(), test1.end()) << endl;

        if (mysearch(test.begin(), test.end(), 10)) cout << "Find 10 in test.\n";
	else cout << "10 not in test.\n";


        if (mysearch(test1.begin(), test1.end(), 2.5)) cout << "Find 2.5 in test1.\n";
	else cout << "2.5 not in test1.\n";

        insertion_sort(test, 0, 7);
        for (int i=0; i<8; i++)
	        cout << test[i] << endl;        

	return 0;
}