Как из алгоритма в итерационном виде сделать рекурсивный

#алгоритм #рекурсия

Есть такой алгоритм для поиска первого вхождения числа с помощью бинарного поиска.

int lower_bound(const vector &mas, const int &value)
{
  int l = 0, r = mas.size() - 1;
  while (l < r)
  {
    int m = l + (r - l)/2;
    if (mas[m] >= value)
      r = m;
    else
      l = m + 1;
  }
  return mas[l] == value ? l : -1;
}


Как его можно записать с помощью рекурсии?
    

Ответы

Ответ 1

Вначале пара замечаний по коду


Никогда не создавайте переменных с именем l. Они неотличимы от 1 и сильно понижают
читабельность кода
Для двоичного поиска переменная m должна вычисляться по формуле

m  = (left + right) / 2


поиск потому и "двоичный", что отрезок делится на равные части


А теперь код

int lower_bound_r(const vector &mas, const int &value, int left, int right) {
  if (left >= right)
    return mas[left] == value ? l : -1;
  int m = (left + right) / 2;
  if (mas[m] >= value)
    right = m;
  else
    left = m + 1;
  return lower_bound_r(mas, value, left, right);
}

int lower_bound(const vector &mas, const int &value) {
  return lower_bound_r(mas, value, 0, mas.size() - 1);
}


Ответ 2

заменить обычный цикл на рекурсивный
к примеру 

void foo(int start, int end) {
    if (start < end) {
       //выполнять тело цикла
       foo(start + 1, end);
    } else {//Конец цикла} 
}


Поиграя с параметрами, таким способом можно заменить любой цикл
Если обобщить то это выглядит так:

 void foo(необходимые параметры) {
        if ( !условие выхода) {
           //выполнять тело цикла
           foo(что то, что участвует в условии выхода из цикла);
        } else {//Конец цикла} 
    }