Рекурсия

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

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

Рекурсия возможна благодаря тому, что при вызове функции создаются новые экземпляры локальных переменных, которые сохраняются во внутреннем стеке машины. Стек функционирует по принципу LIFO - Last In – First Out (последний вошел – первый вышел).

Переменные помещаются в стек одна за другой и выбираются из стека в обратном порядке.

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

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

Рассмотрим пример вычисления факториала 5.

, где - это 4!

т.е 5!=4!5

Факториал нуля равен 1. Отсюда формула вычисления N-факториала:

Реализуем вычисление факториала в виде функции:

#include "stdafx.h"

float fact(int N) //рекурсивная функция вычисления факториала числа N

{

Обращение функции к самой себе

if (N==0)

return 1;

else

return (fact(N-1)*N);

}

void main()

{ int N=15;

printf("факториал 15=%f\n",fact(N)); /* обращение к функции fact для вычисления факториала 15 */

}

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

Пример: Вычислить количество нулей в массиве А[10].

# include "stdafx.h"

const int n=10;

int kol(int i,int *A)

{ if (i==n) return 0;

else {

if(A[i]==0) return kol(i+1,A)+1;

else return kol(i+1,A);

}

}

int main()

{ int y[]={1,0,2,5,4,0,1,3,0,4,3};

int x=kol(0,y);

printf("количество нулей=%d\n",x);

}

Технология сборки библиотеки

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

Заголовочный файл (иногда головной файл, англ. header file), или подключаемый файл, в языках программирования С и C++ - это файл с расширением .h. Заголовочный файл в общем случае может содержать любые конструкции языка программирования, но на практике в него помещают объявления идентификаторов, которые должны быть объявлены более чем в одном файле вашей программы, объявления структур, прототипы функций, перечисления, макросы препроцессора. Основная цель использования заголовочных файлов — вынесение описания нестандартных типов и функций за пределы основного файла с кодом. Заголовочный файл используется путём включения его текста в использующий его файл директивой препроцессора #include. Чтобы избежать повторного включения одного и того же кода, используются директивы #ifndef, #define, #endif.

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

Пусть создаваемая нами библиотека состоит из заголовочного файла mylib.h и файла mylib.cpp.

В заголовочном файле mylib.h содержатся прототипы функций, которые описаны в данном параграфе.

Перечислим все эти функции:

• maximum(). Находит и возвращает наибольшее из двух чисел.

• Form_matrix(). Заполняет матрицу, адрес которой передается ей в качестве параметра, случайными числами.

• ST(). Возводит любое число в степень n.

• Z(). Меняет значение переданного ей параметра на случайное число.

• Sum(). Вычисляет среднее арифметическое вектора, адрес и размер которого передаются в качестве параметров.

• Product(). Вычисляет произведение двух матриц, адреса и размеры которых передаются в качестве параметров. Возвращает матрицу соответствующего размера.

• SM(). Безтиповая функция вычисляет симметричную матрицу из исходной матрицы.

• PK(). Безтиповая функция переводит декартовые координаты точки в полярные.

• CP().Типизированная функция для подсчета количества положительных элементов в любой матрице.

• Mod_Otk(). Типизированная функция находит максимальный компонент и среднее значение в любом массиве.

• fact(). Рекурсивная функция вычисляет факториал числа n.

Текст файла mylib.h:

#ifndef MYLIB_H // если MYLIB_H еще не определили, то определяем

#define MYLIB_H

const nmax = 50; // максимальная размерность матрицы

int maximum(int a, int b);//прототип функции maximum

void Form_matrix(int A[][M], int m, int n); /*прототип функции Form_matrix */

float ST(float x, int n); //прототип функции ST

void Z (int у); //прототип функции Z

void Z (int *у); //прототип функции Z

int Sum ( int A[], int N ); //прототип функции Sum

void product(int А[][nmax], int В[][nmax],int С[][nmax], int m, int n, int k); //прототип функции product

void SM(float Y[4][4], int n, float X[4][4]); /*прототип функции SM */

void PK(float a, float b, float *ro, float *fi); /*прототип функции PK */

int CP(float D[7][7], int m, int n); //прототип функции CP

float Mod_Otk(float *a, int n); //прототип функции Mod_Otk

float fact(int N); //прототип функции fact

#endif /* MYLIB_H */

Файл mylib.cpp является созданной нами библиотекой, в которой содержатся реализации всех перечисленных выше функций.

В целях экономии текст файла mylib.cpp приведем не полностью.

Текст файла mylib.cpp:

#include "stdafx.h"

#include "stdlib.h"

{

int Sum ( int A[], int N )//заголовок функции Sum

{

int i, sum; //локальные переменные

sum = 0;

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

sum += A[i];

return sum/N; //возвращаемое значение

}

void product(int А[][nmax], int В[][nmax],int С[][nmax], int m, int n, int k) //заголовок функции product

{ /* m - число строк в матрице А;     n - число строк в матрице В и число столбцов в матрице А;    k - число столбцов в матрице В.  */

for (int i=0; i< m; i++)       for (int j=0; j< k; j++)

{       С[i][j]=0;       for (int l=0; l< n; l++)

С[i][j] + = А[i][l]*В[l][j];       }      }

float fact(int N) //рекурсивная функция вычисления факториала числа N

{

if (N==0)

return 1;

else

return (fact(N-1)*N);

…

}

Текст файла, использующего созданную библиотеку

#include "mylib.h"//подключение заголовочного файла библиотеки mylib

// главная функция выполняет основную работу программы

int main()

{

int a[nMax][nMax],b[nMax][nMax]; //объявление матриц

SM(a);//вызов функции SM для обработки матрицы a

…

// здесь могут быть обращения к другим функциям библиотеки

return 0; }