Знакомство с рекурсией.

Рекурсия – это прием программирования, при котором программа вызывает саму себя либо непосредственно, либо косвенно.

Как правило, неопытный программист, узнав про рекурсию, испытывает легкое недоумение. Первая мысль – это бессмысленно!!! Такой ряд вызовов превратиться в вечный цикл, похожий на змею, которая съела сама себя, или приведет к ошибке на этапе выполнения, когда программа поглотит все ресурсы памяти.

Однако рекурсия – это превосходный инструмент, который при умелом и правильном использовании поможет программисту решить множество сложных задач.

Пример на рекурсию

Исторически сложилось так, что в качестве первого примера на рекурсию почти всегда приводят пример вычисления факториала.

Что ж, не будем нарушать традиций.

Для начала, вспомним, что такое факториал. Обозначается факториал восклицательным знаком «!» и вычисляется следующим образом:

N! = 1 * 2 * 3 * … * N

Другими словами, факториал представляет собой произведение натуральных чисел от 1 до N включительно. Исходя из вышеописанной формулы, можно обратить внимание наследующую закономерность:

N! = N * (N-1)!

Ура!!! Мы можем найти факториал через сам факториал! Вот здесь мы и попадаемся в ловушку. Наша находка, на первый взгляд, абсолютно бесполезна, ведь неизвестное понятие определяется через такое же неизвестное понятие, и получается бесконечный цикл. Выход из данной ситуации сразу же будет найден, если добавить к определению факториала следующий факт:

1! = 1

Теперь мы можем себе позволить вычислить значение факториала любого числа. Попробуем, например, получить 5!, несколько раз применив формулу N! = N * (N-1)! и один раз формулу 1! = 1:

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

Как же будет выглядеть данный алгоритм, если перенести его на язык С? Давайте, попробуем реализовать рекурсивную функцию:

#include <iostream> using namespace std; long int Fact(long int N) { // если произведена попытка вычислить факториал нуля if (N < 1) return 0; // если вычисляется факториал единицы // именно здесь произведется выход из рекурсии else if (N == 1) return 1; // любое другое число вызывает функцию заново с формулой N-1 else return N * Fact(N-1); } void main() { long number=5; //первый вызов рекурсивной функции long result=Fact(number); cout<<"Result "<<number<<"! is - "<<result<<"\n"; }

Как видите, всё не так уж сложно. Для более детального понимания примера рекомендуем скопировать текст программы в Visual Studio и пошагово пройтись по коду отладчиком.