Веб программирование

Рекурсия [C++]

 
 

Приветствие! Сейчас расскажу о рекурсии.

Недавно я писал функцию, которая вычисляет факториал числа. Велосипеды изобретал, так сказать. Так вот в этой функции и использовалась эта самая рекурсия.

"Рекурсия - это процесс повторения элементов самоподобным образом", говорит нам википедия. Также, если вы попросите кого-то обьяснить вам, что же такое рекурсия, вам наверняка ответят: "чтобы понять рекурсию, нужно сначала понять рекурсию".

Рекурсия - это одна из необьяснимых вещей программирования (ну, или по крайней мере очень труднообьяснимая вещь), в общем смотрите на код и сами все поймете.

Для тех кто в танке, что такое факториал:

Факториал n (обозначается n!) - это произведение всех натуральных чисел от одного до n включительно. Например:

5! = 1*2*3*4*5 = 120

Рекурсивное вычисление факториала:

int fac(int val)
{
    if(val == 1)
       return 1;
    else
       return fac(val - 1) * val;
}

Здесь мы вызываем функцию fac(...) из нее самой. Это и есть знаменитая рекурсия. Теперь давайте построим не менее знаменитую "ханойскую башню".

Ханойская башня

Ханойская башня - это одна из популярных головоломок, цель которой составляет перенести пирамиду из восьми колец на одном стержне на стержень следующий, притом можно ложить только меньшее кольцо на большее и за один раз переносить можно только одно кольцо. Решение головоломки из четырех колец:

4-rings Tower of Hanoi

(картинка взята с Wikipedia)

Я решил эту головоломку так:

#include <iostream>

using namespace std;

void tower(int r, int b, int e)
{
  int c;
  if (((b == 1) && (e == 2)) || 
      ((b == 2) && (e == 1)))
    c = 3;
  else
  if (((b == 1) && (e == 3)) || 
      ((b == 3) && (e == 1)))
    c = 2;
  else
  if (((b == 2) && (e == 3)) || 
      ((b == 3) && (e == 2)))
    c = 1;
  if (r > 1)
  {
    tower(r - 1, b, c);
    cout << b << " > " << e << endl;
    tower(r - 1, c, e);
  }
  else
    cout << b << " > " << e << endl;
}

int main()
{
    tower(3, 1, 3);
}

Скомпилируйте:

g++ hanoi.cpp -o hanoi

Ну а на этом все. Удачи вам!


Есть вопросы? Спроси на нашем форуме!!
Нет комментариев

Оставлять комментарии можно только зарегистрированным




Предупреждение: Вся информация представлена исключительно в образовательных целях.
Ни авторы, ни администрация не несут ответственности в случае ее использования в противозаконных целях.