Recursive Algorithms

1. Sum of elements of array using recursion

	#include <iostream>
	using namespace std;
	int location_in_array = 0;
	int array[] = {1, 2, 3, 4, 5, 6};
	int do_sum(int array[], int sum)
	{
	//Terminate when reached end of array
	if(location_in_array >= (sizeof(array) - 1))
	{
	return sum += array[location_in_array];
	}
	sum += array[location_in_array];
	location_in_array++;
	return do_sum(array, sum);
	}
	int main()
	{
	cout << "Sum is " << do_sum(array, 0) << "\n";
	return 0;
	}

view raw ArraySum_Recursion.c hosted with ❤ by GitHub

2. Array - Linear Search

	#include <iostream>
	using namespace std;
	int search_value = 3;
	int array[] = { 1, 2, 3, 4, 5, 6 };
	int size = sizeof(array) / sizeof(*array);
	int do_linear_search(int array[], int index, int size)
	{
	//Recursion termination condition
	if(index >= size)
	{
	return -1; //No match found
	}
	else if(array[index] == search_value)
	{
	cout <<"Match found!" <<endl;
	return index; //Match found
	}
	else
	{
	//Perform Recursion
	do_linear_search(array, ++index, size);
	}
	}
	int main ()
	{
	cout << "Match was found at index " << do_linear_search (array, 0, size) << "\n";
	return 0;
	}

view raw Array_LinearSearch.c hosted with ❤ by GitHub

3. Array - Binary Search

	#include <iostream>
	using namespace std;
	int input_array[] = {1,2,3,4,5,6,7,8,9,10};
	int size = 10;
	int search_value = 10;
	int guess_value = size/2;
	int max_value = size-1;
	int min_value = 0;
	int do_binary_search(int array[], int guess, int min, int max)
	{
	//Recursion termination
	if(guess > max || guess < min)
	{
	return -1; //No match found
	}
	else if(search_value < input_array[guess])
	{
	max = guess - 1;
	guess = (max - min) / 2;
	return do_binary_search(array, guess, min, max);
	}
	else if(search_value > input_array[guess])
	{
	min = guess + 1;
	guess = min + ((max - min) / 2);
	return do_binary_search(array, guess, min, max);
	}
	else //input_array[guess] == search_value
	{
	return guess; //Match found
	}
	}
	int main()
	{
	cout << "Binary search result " << do_binary_search(input_array, guess_value, min_value, max_value) << endl;
	return 0;
	}

view raw Array_BinarySearch.c hosted with ❤ by GitHub