На этом шаге мы разберем несколько примеров использования рекурсии при решении задач.

Пример 1. Вычисление факториала.

#include<iostream.h>
void main ()
{
      int  factorial(int), n;
      cout << "Задайте число: ";
      cin >> n;
      cout << n << "! = " << factorial(n);
}
/* ----------------------- */
int factorial (int n)
{
      return (n>1)?n*factorial(n-1):1;
}

Текст этой программы можно взять здесь.

Пример 2. Выдать на печать в обратном порядке цифры целого положительного числа N.

#include<iostream.h>
void main ()
   {
      int REVERSE (int), n;
      cout << "Введите целое положительное число...";
      cin >> n;
      REVERSE(n);
   }
/* --------------------- */
int REVERSE (int n)
{
      cout << n%10;
      if  (n/10!=0)
         REVERSE (n/10);
}

Текст этой программы можно взять здесь.

Пример 3. Вычисление наибольшего общего делителя.

#include<iostream.h>
void main ()
{
      int NOD(int *,int *),x,y;
      /* --------------------- */
      cout << "Найдем НОД...\n";
      cout << "Введите x: "; cin >> x;
      cout << "Введите y: "; cin >> y;
      cout << "НОД(" << x << "," << y << ") = " << NOD(&x,&y);
}
/* ------------------- */
int NOD (int *u,int *v)
{
      int k1,k2;
      cout << "Вошли в процедуру... " << *u << " " << *v << endl;
      if  (*u==0)
         return *v;
      else
      {
         int k1 = *v%*u, k2 = *u;
         return NOD(&k1,&k2);
      }
 }

Текст этой программы можно взять здесь.

Пример 4. Возведение в степень (без использования указателей).

#include<iostream.h>
void main ()
{
      int x,y,pow(int,int);
      /* -------- */
      cout << "Возведение в степень...\nВведите x, y: ";
      cin >> x >> y;
      cout << x << " в степени " << y << " = " << pow(x,y);
   }
/* --------- */
int pow (int m,int n)
{
      if  (n==0) return 1;
      else
         return m*pow(m,n-1);
}

Текст этой программы можно взять здесь.

Пример 5. Возведение в степень (с использованием указателей).

#include<iostream.h>
void main ()
{
      int x,y,pow(int*,int*);
      int *px=&x,*py=&y;
      /* ----------------------------------------------------- */
      cout << "Возведение в степень...\nВведите x, y: ";
      cin >> x >> y;
      cout << pow(px,py);
}
/* --------- */
int pow (int *m,int *n)
{
      if  (*n==0) return 1;
      else
      {
         cout << "Вошли в процедуру... ";
         cout << *m << " " << *n << endl;
         (*n)--;
         return (*m) * pow(m,n);
      }
}

Текст этой программы можно взять здесь.

Пример 6. Возведение в степень (с использованием ссылок).

#include<iostream.h>
void main ()
{
      int x,y,pow(int&,int&);
      /* ----------------------------------------------------- */
      cout << "Возведение в степень...\nВведите x, y: ";
      cin >> x >> y;
      cout << pow(x,y);
}
/* --------- */
int pow (int& m,int& n)
{
      if  (n==0) return 1;
      else
      {
         cout << "Вошли в процедуру... ";
         cout << m << " " << n << endl;
         n--;
         return m * pow(m,n);
      }
}

Текст этой программы можно взять здесь.

Пример 7. Вычисление чисел Фибоначчи. В 1202 году итальянский математик Фибоначчи решил такую задачу: "Пара кроликов каждый месяц дает приплод двух кроликов (самку и самца), которые через два месяца способны давать новый приплод. Сколько кроликов будет через год, если в начале года имели пару кроликов?"

Решение. В начале построим математическую модель данной задачи. Символом F_n обозначим число пар кроликов, которое будем иметь через n месяцев, отсчитывая от начала года. По условию задачи в начале года имели одну пару кроликов, а через месяц - две пары.

Значит, F₀=1, F₁=2. После второго месяца получим в приплоде только одну пару, т.е. столько, сколько имели в начале года. Следовательно, F₂=F₀+F₁.

Рассуждая аналогично, получим следующую зависимость: F_n=F_n-2+F_n-1. А теперь - программа на языке C++:

#include<iostream.h>
void main ()
{
      int f(int);
      for (int k=1; k<=12; k++)
         cout << f(k) << " ";
   }
/* --------------- */
int f (int n)
{
      if  (n==0) return 1;
      else
          return (n==1)? 2 : f(n-2) + f(n-1);
}

Текст этой программы можно взять здесь.

Пример 8. Программа вычисления значения функции целочисленного аргумента, рекурсивное определение которой имеет вид:

                         N-3,        если N>23,
                 F(N) =  
                         F(F(n+4)),  если N<=23.

Можно легко показать, что значением функции F(N) является максимальное из двух чисел N-3 и 21, т.е. F(N) = max(N-3,21).

Действительно,
при N>23 это очевидно, т.к. F(N)=N-3<=21;
при 20<=N<=23 F(N)=F(F(N+4))=F(N+1)=21, т.к. N+4>23;
при N<20 F(N)=21, т.к. для любого N<=20 существует такое m>0, что аргумент функции N принадлежит отрезку [20-4*m,23-4*m], который вследствие косвенной рекурсии всегда сводится к интервалу [20,23].

#include<iostream.h>
void main ()
{
      int f(int),n;
      cout << "Введите аргумент... "; 
      cin >> n;
      cout << "Результат... " << f(n);
}
/* -------------- */
int f(int n)
{
      return n>23 ? n-3: f(f(n+4));
}

Текст этой программы можно взять здесь.

Пример 9. Реализация алгоритма быстрой сортировки Ч.Хоара.

#include<iostream.h>
void main ()
{
      int a[5],m=0,n=4;
      void quicksort (int *,int,int);
      /* ------------- */
      for (int i=0; i<5; i++)
      {
         cout << "Вводите " << i+1 << " элемент массива: ";
         cin >> a[i];
      }
      int *pa = &a[0];
      for (i=0; i<5; i++)
         cout << i+1 << "-й элемент массива: " << *(pa+i) << endl;
      quicksort (pa,m,n);
      for (i=0; i<5; i++)
         cout << i+1 << "-й элемент массива: " << *(pa+i) << endl;
}
/* ----------------------------- */
void quicksort (int *pa,int l,int u)
{
      int i,j,temp;
      void partition (int *,int,int,int *,int *);
      /* --------------------------------------- */
      cout << "Вошли в функцию quicksort... \n";
      partition (pa,l,u,&i,&j);
      if  (l < j)
         quicksort (pa,l,j);
      if  (i < u)
         quicksort (pa,i,u);
}
/* ------------------------- */
void partition (int *pa,int l,int u,int *ri,int *rj)
{
      int i = l, j = u, r = *(pa+(l+u)/2);
      while (i<=j)
      {
         while (*(pa+i)<r)
            i++;
         while (*(pa+j)>r)
            j--;
         if  (i<=j)
         {
            int temp = *(pa+i); 
            *(pa+i) = *(pa+j);
            *(pa+j) = temp; i++; j--;
         }
      }
      *ri = i; *rj = j;
}

Текст этой программы можно взять здесь.

На следующем шаге мы продолжим изучение функций, в частности, разберем функции с переменным количеством параметров.

Предыдущий шаг Содержание Следующий шаг