Рекурсивные функции в С++

      Комментарии к записи Рекурсивные функции в С++ отключены

Помечено: ,

В этой теме 0 ответов, 1 участник, последнее обновление  Васильев Владимир Сергеевич 3 мес., 4 нед. назад.

  • Автор
    Сообщения
  • #3723

    Под рекурсивной функцией в программирование понимают функцию, которая вызывает сама себя. Рекурсивные функции чаще всего используют для компактной реализации рекурсивных алгоритмов. Классическими рекурсивными алгоритмами могут быть возведение числа в целую положительную степень, вычисление факториала. Обширную теорию по рекурсивным функциям в программировании можно прочитать в статье «Рекурсия в программировании. Анализ алгоритмов«. На практике все может казаться проще, т.к. рекурсивную функцию написать очень легко:
    void foo() { return foo(); }
    Сложнее заставить ее делать то, что нам нужно (функция приведенная выше зациклится). Чаще всего корректная рекурсивная функция выглядит следующим образом:

    int foo(int x, int y) {
      if (x > y) {
        return 1; // элементарное решение
      }
      // ... какие-то действия, уменьшающие объем задачи
      // в данном случае - увеличивающие x или уменьшающие y
      x*=2;
      int z = foo(x, y);
      // какие-то действия над результатом
      return z*2;
    }

    Этот пример полностью абстрактен, но он показывает что в начале рекурсивной функции обычно выполняется проверка условия, проверяющего возможно ли решить задачу (аргументы функции задают условия задачи) без рекурсии. Если без рекурсии обойтись нельзя — то исходная задача упрощается и рекурсивно решается более простая, затем над полученным результатом производят какие-то действия, позволяющие из решения более простой задачи получить решение более общей.

    Перейдем к более практичному примеру применения рекурсивной функции.

    Задача: Вычислить факториал числа n.

    Для справки: «Факториалом числа N называют произведение всех натуральных чисел от 1 до N»

    #include "stdafx.h"
    #include <iostream>
    using namespace std;
    long int factorial(int n) {
      if (n<=1)
        return (n);
      else return(n*factorial(n-1));
    }
    
    int main () {
      int i; long int f;
      cout<<"i=";
      cin>>i;
      f=factorial(i);
      cout<<i<<"!="<<f<<endl;
      system("pause");
      return 0;
    }

Для ответа в этой теме необходимо авторизоваться.