Теоретические сведения

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

В языках программирования процедурной парадигмы предусмотрено использование рекурсивных функций в решении задач.

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

Пример 1. В арифметической прогрессии найдите a_n, если известны а₁= -2.5, d=0.4, не используя формулу n-го члена прогрессии.

По определению арифметической прогрессии, a_n= a_n-1+ d, при этом

a_n-1= a_n-2+ d, a_n-2= a_n-3+ d,… a₂= a₁+ d.

Таким образом, нахождение a_n для номера n сводится к решению аналогичной задачи, но только для номера n-1, что в свою очередь сводится к решению для номера n-2, и так далее, пока не будет достигнут номер 1 (значение а₁дано по условию задачи).

float arifm (int n, float a, float d) {

if (n<1) return 0; // для неположительных номеров

if (n==1) return a; // базовый случай: n=1

return arifm(n-1,a,d)+d; // общий случай

}

Пояснение к примеру.

В рекурсивных функциях несколько раз используется return.В базовом случае возвращается конкретный результат (в примере – значение а), а общий случай предусматривает вызов функцией себя же, но с меняющимися значениями отдельных параметров (в примере изменяется только номер члена последовательности, при этом не меняются разность и первый член прогрессии).

Для решения задач рекурсивными методами разрабатывают следующие этапы, образующие рекурсивную триаду:

● параметризация – выделяют параметры, которые используются в решении;

● база рекурсии – определяют тривиальный случай, при котором решение очевидно;

● декомпозиция – выражают общий случай через подзадачи с измененными параметрами.

Пример 2. Для целого неотрицательного числа n найдите его факториал.

Разработаем рекурсивную триаду.

Параметризация: n – неотрицательное целое число.

База рекурсии: для n=0 факториал равен 1.

Декомпозиция: n!=(n-1)!*n.

long factor (int n) {

if (n<0) return 0; // для отрицательных чисел

if (n==0) return 1; // базовый случай: n=0

return factor(n-1)*n; // общий случай (декомпозиция)

}

Целесообразность применения рекурсии в программировании обусловлена спецификой задач, в постановке которых явно или опосредовано указывается на возможность сведения задачи к подзадачам, аналогичным самой задаче.

Пример 3. Дан прямоугольник, стороны которого выражены натуральными числами. Разрежьте его на минимальное число квадратов с натуральными сторонами.

#include <stdio.h>

int kv(int m,int n);

void main(){

int a,b,k;

printf("Введите стороны прямоугольника->");

scanf("%d%d",&a,&b);

k = kv(a,b);

printf("Прямоугольник со сторонами %d и %d можно

разрезать на %d квадратов",a,b,k);

}

int kv(int m,int n){

if(m==n) return 1;

if(m>n) return 1+kv(m-n,n);

return 1+kv(m,n-m);

}