Как работает рекурсия – объяснение в блок-схемах и видео.

2.6 Лабораторная работа №6. Программирование с использованием функций. Рекурсивная функция

Цель работы: познакомиться с понятиями "функция", «рекурсивная функция» в языке программирования С, закрепить практические навыки программирования на примере реализации алгоритмов при помощи функций, рекурсивных функций, научиться применять метод последовательной детализации в практическом программировании, применять функции при решении задач.

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

Общие сведения

Особенностью языка программирования Си является то, что программы на Си строятся из блоков, называемых функциями.

Функция является отдельным именованным фрагментом программного кода на С, выполняющим конкретную специфическую задачу. Сама по себе функция напоминает отдельную программу на С.

Все функции распадаются на две большие категории: те, что программисты сами пишут и те, которые уже имеются в пакете компилятора С. Первые называются функциями, определенными пользователем; вторые – библиотечными функциями. Функциями удобно пользоваться, например, если необходимо обработать один и тот же код программы или когда большая задача, которую можно расчленить на конкретные маленькие или элементарные, простейшие задачи, которые часто возникают во многих реальных задачах.

Для объявления функции используется следующий синтаксис:

<тип> <имя функции> ([список параметров]) { <тело функции> }

Тип определяет возвращаемый тип функции. Имя функции служит для ее вызова в программе и ее правило определения совпадает с правилом определения имен переменных. Список параметров необходим для передачи функции каких-либо данных при ее вызове. Телов функции – это набор операторов, которые выполняются при ее вызове.

Пример задания функции.

double square(double x)

{ double sq1, sq2, arg = 5;

sq1=square(arg);

В данном примере задается функция с именем square, которая принимает один входной параметр типа double, возводит его в квадрат и возвращает вычисленное значение вызывающей программе с помощью оператора return.

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

В языке С допускается чтобы функция вызывала саму себя. Этот процесс называется рекурсией. В некоторых задачах программирования такой подход позволяет заметно упростить создаваемый программный код. Рассмотрим данный процесс на следующем примере.

Пример использования рекурсивных функций.

#include

void up_and_down(int);

{up_and_down(1);

void up_and_down(int n)

{printf(“Уровень вниз %d ”,n);

if(n < 4) up_and_down(n+1);

printf(“\n”);

printf(“Уровень вверх %d\n”,n);

Результатом работы этой программы будет вывод на экран следующих

Уровень вниз 1 Уровень вниз 2 Уровень вниз 3 Уровень вниз 4

Уровень вверх 4 Уровень вверх 3 Уровень вверх 2 Уровень вверх 1

Полученный результат работы программы объясняется следующим образом. Вначале функция main() вызывает функцию up_and_down() с аргументом 1. В результате аргумент n данной функции принимает значение 1 и функция printf() печатает первую строку. Затем выполняется проверка и если n < 4, то снова вызывается функция up_and_down() с аргументом на 1 больше n+1. В результате вновь вызванная функция печатает вторую строку. Данный процесс продолжается до тех пор, пока значение аргумента не станет равным 4. В этом случае оператор if не сработает и вызовется функция printf(), которая печатает пятую строку «Уровень вверх 4». Затем функция завершает свою работу и управление передается функции, которая вызывала данную функцию. Эта функция up_and_down() с аргументом n=3, которая также продолжает свою работу и переходит к оператору printf(), который печатает 6 строку «Уровень вверх 3». Этот процесс продолжается до тех пор, пока не будет достигнут исходный уровень, т.е. первый вызов функции up_and_down() и управление вновь будет передано функции main(), которая завершит работу программы.

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

Переменные, объявляемые внутри функции, называются локальными переменными. Имя и значение локальной переменной известны только функции, внутри которой переменная объявлена.

В дополнение к локальным переменным C позволяет вашим программам объявлять глобальные переменные, которые известны на протяжении всей программы (глобально для всех функций). Глобальная переменная объявляется в начале исходного файла вне какой-либо функции.

Задание А

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

Пример

Дана целочисленная матрица размером 8 на 8. Найти:

такие k , что k -я строка матрицы совпадает с k -м столбцом;

сумму элементов в тех строках, которые содержат хотя бы один отрицательный элемент.

Блок-схема решения задачи дана в Лабораторной работе №5

Программа имеет следующий вид

#include

/* Объявление прототипов функций */

void func(int *mat, int m, int n);

void func2(int *mat, int m, int n);

int main(int argc, char* argv)

{int i, j,matrix;

/* Объявляем и инициализируем матрицу 8х8 */

/* генератором случайных чисел заполняем матрицу */

for (i = 0; i < m1; i++)

for (j = 0; j < n1; j++)

matrix[i][j]=rand()%10-1;

printf("\n Сгенерированная матрица имеет вид:\n ");

/* вывод матрицы */

for (i = 0; i < m1; i++)

{ for (j = 0; j < n1; j++)

printf(“%d “,matrix[i][j]);

func1(&matrix, 8, 8);

func2(&matrix, 8, 8);

system("PAUSE");/* задержка экрана*/

void func1(int *mat, int m, int n)

{ int i, j, p; /* Счетчик и признак совпадения */

for (i = 0; i < m; i++)

for (j = 0; j < n; j++)

/* Сравниваем элемент i-й строки j-го столбца с элементом j-й строки i-го столбца. В случае их несоответствия присваеваевам Флагу значение Ложь и прерываем цикл по j конструкцией break */

if (mat != mat)

printf("\n \t\t\tРЕЗУЛЬТАТ ФУНКЦИИ №1");

/* выводим на экран номер соответствующей строки */

if (p==1) printf("i=%d ", i);

} if (p==0) printf("\n нет одинаковых строк и столбцов ");

void func2(int *mat, int m, int n)

int i, j; /* Счетчик и переменная для хранения суммы */

int p1, iSumm; /* признак нахождение отрицательного элемента и переменная для хранения суммы */

printf("\n \t\t\tРЕЗУЛЬТАТ ФУНКЦИИ №2\n");

for (i = 0; i < m; i++)

{ /* Присваеваем переменным исходные значения */

for (j = 0; j < n; j++)

{/* При нахождение хотя бы одного отрицательного элемента присваиваем p1 = 1, обозначающее необходимость вывода Суммы на экран */

if (mat < 0) p1 = 1;

/* Суммируем значения элементов i-й строки */

iSumm += mat;

/* В случае нахождения в строке хотя бы одного отрицательного элемента выводим на экран сумму элементов i-й строки */

if (p1) printf("Summ of elements of row #%d = %d\n", i, iSumm);

Сгенерированная матрица имеет вид

1 0 7 6 0 -8 3 5

8 2 4 9 1 -6 4 9

РЕЗУЛЬТАТ ФУНКЦИИ №1

Совпавшие строки и столбцы

РЕЗУЛЬТАТ ФУНКЦИИ №2

Сумма элементов строки #1 = 14

Сумма элементов строки #5 = 31

Варианты задания А

Варианты задания А соответствуют вариантам задания А лабораторной работы №5

Задание Б

Выполнить упражнения из раздела «Лабораторная работа №3 Программирование циклических алгоритмов», используя рекурсивную функцию, вычисляющую факториал

Задание: Составить программу вычисляющую:

Блок-схема решения задачи дана в Лабораторной работе №3

Программа имеет следующий вид

#include

long fact(int m)

{ if (m<=1) return (1);

else return (m * fact (m -1)); // функция fact вызывает саму себя

printf ("\n Введите значение n\n n=");

scanf ("%d", &n);

printf ("\n Введите значение x\n x=");

scanf ("%d", &x);

for (i=1; i<=n; i++)

S=S+(cos(i*x)/ f);}

printf ("\n Сумма S=%f", S);

Результат выполнения программы:

Введите значение n

Введите значение x

Сумма S=0.139995

Варианты задания Б

Варианты задания Б соответствуют вариантам задания А лабораторной работы №3

Контрольные вопросы

Для чего нужны в программе процедуры и функции?

В чем отличие между процедурой и функцией?

Чем отличаются формальные и фактические параметры?

Чем отличаются параметры-значения и параметры-переменные?

Как объявляются глобальные и локальные переменные? Каково правило видимости этих переменных?

Почему при обращении к процедуре, аргумент, передаваемый параметру-переменной, может быть только переменной, а не константой или выражением?

Завершается ли работа функции при вызове оператора return?

Как называется функция, которая вызывает саму себя?

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

Пример — функция, вызывающая себя:

< 1) return; function(value - 1); printf("%d ",value); }

Пример — функция, которая вызывает другую функцию, которая в свою очередь, вызывает ее снова:

int function(int value) { if(value < 1) return; function(value - 1); printf("%d ",value); }

Свойства

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

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

Реализация

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

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

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

Анализ рекурсии

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

Сложность по времени

Чтобы подсчитать время работы алгоритма на основе итераций, мы используем количество операций. С рекурсией все аналогично: мы пытаемся выяснить процессорное время, за которое выполняется рекурсивный вызов. Вызов функции 0(1) , следовательно (n) — количество рекурсивных вызовов, которые выполнит рекурсивная функция 0(n) .

Вычислительная сложность

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

Перевод статьи “Data Structure — Recursion Basics ” был подготовлен дружной командой проекта .

Хорошо Плохо

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

Представляю вашему вниманию перевод статьи Beau Carnes How Recursion Works - explained with flowcharts and a video .

«Для того чтобы понять рекурсию, надо сначала понять рекурсию»

Рекурсию порой сложно понять, особенно новичкам в программировании. Если говорить просто, то рекурсия – это функция, которая сама вызывает себя. Но давайте попробую объяснить на примере.

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

Вы открываете коробку только чтобы найти… еще больше коробок. Коробки внутри коробок и вы не знаете, в какой из них Ваш ключ. Вам срочно нужна рубашка, так что вам надо придумать хороший алгоритм и найти ключ.

Есть два основных подхода в создании алгоритма для решения данной проблемы: итеративный и рекурсивный. Вот блок-схемы этих подходов:

Какой подход для Вас проще?

В первом подходе используется цикл while. Т.е. пока стопка коробок полная, хватай следующую коробку и смотри внутрь нее. Ниже немного псевдокода на Javascript, который отражает то, что происходит (Псевдокод написан как код, но больше похожий на человеческий язык).

function look_for_key(main_box) { let pile = main_box.make_a_pile_to_look_through(); while (pile is not empty) { box = pile.grab_a_box(); for (item in box) { if (item.is_a_box()) { pile.append(item) } else if (item.is_a_key()) { console.log("found the key!") } } } }

В другом подходе используется рекурсия. Помните, рекурсия – это когда функция вызывает саму себя. Вот второй вариант в псевдокоде:

function look_for_key(box) { for (item in box) { if (item.is_a_box()) { look_for_key(item); } else if (item.is_a_key()) { console.log("found the key!") } } }

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

Поскольку рекурсия используется во многих алгоритмах, очень важно понять как она работает. Если рекурсия до сих пор не кажется Вам простой, не беспокойтесь: Я собираюсь пройтись еще по нескольким примерам.

Граничный и рекурсивный случай

То, что Вам необходимо принять во внимание при написании рекурсивной функции – это бесконечный цикл, т.е. когда функция вызывает саму себя… и никогда не может остановиться.
Допустим, Вы хотите написать функцию подсчета. Вы можете написать ее рекурсивно на Javascript, к примеру:

// WARNING: This function contains an infinite loop! function countdown(i) { console.log(i) countdown(i - 1) } countdown(5); // This is the initial call to the function.

Эта функция будет считать до бесконечности. Так что, если Вы вдруг запустили код с бесконечным циклом, остановите его сочетанием клавиш «Ctrl-C». (Или, работая к примеру в CodePen, это можно сделать, добавив “?turn_off_js=true” в конце URL.)

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

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

Function countdown(i) { console.log(i) if (i <= 1) { // base case return; } else { // recursive case countdown(i - 1) } } countdown(5); // This is the initial call to the function.

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

Сначала мы выведем цифру 5, используя команду Console.Log . Т.к. 5 не меньше или равно 1, то мы перейдем в блок else . Здесь мы снова вызовем функцию и передадим в нее цифру 4 (т.к. 5 – 1 = 4).

Мы выведем цифру 4. И снова i не меньше или равно 1, так что мы переходим в блок else и передаем цифру 3. Это продолжается, пока i не станет равным 1. И когда это случится мы выведем в консоль 1 и i станет меньше или равно 1. Наконец мы зайдем в блок с ключевым словом return и выйдем из функции.

Стек вызовов

Рекурсивные функции используют так называемый «Стек вызовов». Когда программа вызывает функцию, функция отправляется на верх стека вызовов. Это похоже на стопку книг, вы добавляете одну вещь за одни раз. Затем, когда вы готовы снять что-то обратно, вы всегда снимаете верхний элемент.

Я продемонстрирую Вам стек вызовов в действии, используя функцию подсчета факториала. Factorial(5) пишется как 5! и рассчитывается как 5! = 5*4*3*2*1 . Вот рекурсивная функция для подсчета факториала числа:

function fact(x) { if (x == 1) { return 1; } else { return x * fact(x-1); } }

Теперь, давайте посмотрим что же происходит, когда вы вызываете fact(3) . Ниже приведена иллюстрация в которой шаг за шагом показано, что происходит в стеке. Самая верхняя коробка в стеке говорит Вам, что вызывать функции fact , на которой вы остановились в данный момент:

Заметили, как каждое обращение к функции fact содержит свою собственную копию x. Это очень важное условие для работы рекурсии. Вы не можете получить доступ к другой копии функции от x .

Нашли уже ключ?

Давайте кратенько вернемся к первоначальному примеру поиска ключа в коробках. Помните, что первым был итеративный подход с использованием циклов? Согласно этому подходу Вы создаете стопку коробок для поиска, поэтому всегда знаете в каких коробках вы еще не искали.

Но в рекурсивном подходе нет стопки. Так как тогда алгоритм понимает в какой коробке следует искать? Ответ: «Стопка коробок» сохраняется в стеке. Формируется стек из наполовину выполненных обращений к функции, каждое из которых содержит свой наполовину выполненный список из коробок для просмотра. Стек следит за стопкой коробок для Вас!

И так, спасибо рекурсии, Вы наконец смогли найти свой ключ и взять рубашку!

Вы также можете посмотреть мое пятиминутное видео про рекурсию. Оно должно усилить понимание, приведенных здесь концепций.

Заключение от автора

Надеюсь, что статья внесла немного больше ясности в Ваше понимание рекурсии в программировании. Основой для статьи послужил урок в моем новом видео курсе от Manning Publications под названием

Алгоритмы

Представляю вашему вниманию перевод статьи Beau Carnes How Recursion Works - explained with flowcharts and a video .

«Для того чтобы понять рекурсию, надо сначала понять рекурсию»

Какой подход для Вас проще?

function look_for_key(box) { for (item in box) { if (item.is_a_box()) { look_for_key(item); } else if (item.is_a_key()) { console.log("found the key!") } } }

Граничный и рекурсивный случай

// WARNING: This function contains an infinite loop! function countdown(i) { console.log(i) countdown(i - 1) } countdown(5); // This is the initial call to the function.

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

Function countdown(i) { console.log(i) if (i <= 1) { // base case return; } else { // recursive case countdown(i - 1) } } countdown(5); // This is the initial call to the function.

Стек вызовов

function fact(x) { if (x == 1) { return 1; } else { return x * fact(x-1); } }

Нашли уже ключ?

И так, спасибо рекурсии, Вы наконец смогли найти свой ключ и взять рубашку!