Рекурсивная функция - C++ [требует правки]

Подходите к рекурсивным функциям как "как решить эту задачу, решая задачу меньшего размера"? И - ко всем функциям - с требованием, чтобы функция выполняла одно логическое действие. Ваша функция и ищет, и выводит ответ - это совершенно разные вещи.

Итак, есть массив, его длина, значение ключа. Как мы ищем элемент? Давайте пойдем с конца (чтоб не мучиться со смещением индекса от начала). Если последний элемент массива - тот, что нам нужен - вернем его. Если нет - будем искать в массиве на один элемент меньшем:

int find(int* array, int size, int key)
{
    if (array[size-1] == key) return size-1; // Искомый элемент найден
    // Иначе ищем его среди `size-1` элементов
    return find(array,size-1,key);
}

Все? Нет, потому что нужно еще решить, что делать, если элемент не найден (d этом случае наша функция будет все время вызывать себя - получится бесконечная рекурсия). Так как индексы меньше 0 не бывают, давайте возвращать -1 как признак отсутствия. Когда мы знаем, что элемента нет? При поиске в пустом массиве. Так что нужно сначала добавить проверку

if (size == 0) return -1; // не найден

Итак, окончательно:

int find(int* array, int size, int key)
{
    if (size == 0) return -1; // Не найден
    if (array[size-1] == key) return size-1; // Искомый элемент найден
    // Иначе ищем его среди `size-1` элементов
    return find(array,size-1,key);
}

Все. Теперь вывод организовываем в другой функции, например,

void find_message(int* array, int index)
{
    if (index < 0) 
    {
        cout << "Key not found\n"; return;
    }
    cout << "Key " << array[index] << : was found in position " << index << endl;
}

Ну, а в main() или еще где...

int array[SIZE] = ...
...
int idx = find(array,SIZE,key);
find_message(array,idx);