Начинающие программисты обычно не любят использовать рекурсию. В частности из-за непонимания, где именно нужно нужно её применять. Притом, что понятие рекурсии довольно простое.

Рекурсия - вызов функцией самой себя.

Мы уже сталкивались с рекурсией при создании программы pseudo_game. Там нам нужно было "поймать" ввод с клавиатуры.

При нажатии клавиши посылается код этой клавиши. Обычно, это 1 байт. Но на клавиатуре есть клавиши с расширенными кодами - 2 байта.

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

void get_input()
{
	char in;
	in = _getch();
	in = _getch(); 
}

При нажатии одной из стрелочек первый вызов _getch считает в in значение -32. А второй вызов одно из значений: 75, 77, 80, 72. Заметьте, что пользователь нажимает клавишу только один раз, а функция _getch вызывается два раза!!!

Но если пользователь нажмёт какую-нибудь клавишу с кодом в один байт, то ему нужно будет ввести ещё какое-нибудь значение. Вот здесь как раз можно воспользоваться рекурсией:

void get_input()
{
	  char in;
	  in = _getch();
	
	  int act = static_cast(in);
	
	  switch (act)
	  {
		  case -32:
		    get_input();
		    break;
		  case 27:
		    // нажата клавиша Esc
		    break;
		  case 75:
		    // нажата стрелочка влево
		    break;
		  case 77:
		    // нажата стрелочка вправо
		    break;
	  }
}

Если пользователь нажал какую-нибудь стрелочку, то сначала посылается код -32. Функция get_input будет вызвана ещё раз. В ней вызывается _getch, но на этот раз в блоке case обрабатывается 77 или 75.

Даже если бы клавиши стрелочек посылали четыре байта: -32, -32, -32, 75. То код всё равно будет работать правильно. Просто функция get_input будет вызвана четыре раза.
Ханойские башни

Ханойские башни - классический пример, который рассматривают при изучении рекурсии.

Итак, у нас есть три стержня. На первом стержне расположено некоторое количество дисков образующих пирамиду, т.е. внизу находятся большие диски, наверху - маленькие. Два других стержня пустые. Нужно перенести все диски на третий стержень, при этом диски должны располагаться в том же порядке, что и на первом стержне. Переносить можно по одному диску за раз. Кроме того, нельзя более большие диски класть на более маленькие.

Рассмотрим пример для трёх дисков. Первый диск перекладываем на третий стержень. Второй диск перекладываем на второй. Первый перекладываем на второй. Третий диск перекладываем на третий стержень. Первый диск перекладываем на первый. Второй перекладываем на третий стержень. И наконец первый диск перекладываем на третий стержень.

Понятно, что чем больше дисков, тем больше перестановок нужно совершить.

Реализация данного алгоритма будет следующей:

void Towers (int number, int from, int to, int free)
{
	  if (number != 0)
	  {
	    Towers (number-1, from, free, to);
	    cout << "Передвигаем " << number << "-й диск  с "
	         << from << "-его стержня  на " << to << "-ий \n";
	    Towers (number-1, free, to, from);
	  }
}

Не буду подробно объяснять данный алгоритм. Вам будет проще понять как он работает, если запустите программу в которой вызывается данная функция и проследите за её выполением. Например:

Towers (3,1,3,2);

Объясню лишь назначение аргументов. number - количество дисков, которое нужно передвинуть. from - стержень с которого нужно передвинуть диски. to - стержень на который нужно передвинуть диски. free - свободный стержень.