Рекурсия
В теле функции известны все объекты, описанные во внешнем блоке, т.е. все глобальные переменные и имя самой функции.
Таким образом, внутри любой функции можно вызывать любую доступную функцию, в том числе и саму себя. Ситуация, когда функция вызывает саму себя, называется рекурсия.
Рекурсия возможна благодаря тому, что при вызове функции создаются новые экземпляры локальных переменных, которые сохраняются во внутреннем стеке машины. Стек функционирует по принципу LIFO - Last In – First Out (последний вошел – первый вышел).
Переменные помещаются в стек одна за другой и выбираются из стека в обратном порядке.
Обязательным элементом всякого рекурсивного процесса является утверждение, определяющее условие завершения рекурсии. Оно называется опорным условием рекурсии.
Если опорное условие выполняется, то может быть задано некоторое фиксированное значение, заведомо достижимое в ходе вычисления. Это позволит организовать своевременную остановку рекурсивного процесса.
Рассмотрим пример вычисления факториала 5.
,
где
-
это 4!
Т.е
5!=4!
5
Факториал нуля равен 1. Отсюда формула вычисления N-факториала:
Реализуем вычисление факториала в виде функции:
#include "stdafx.h"
float fact(int n)
{
if (n==0)
return 1;
else
return (fact(n-1)*n);
}
void main()
{
printf("факториал 5=%f\n",fact(5));
}
Примеры программирования задач с использованием подпрограмм
При программировании задач возможны несколько вариантов. Выбор правильного (более эффективного и надежного) варианта зависит от опыта программиста
Задача 1
Даны
два вектора:
=
{хi};
i
=
и
={yi};i
=
.
Вычислить значение:D
=
,
где
;
;
тх,
ту -
максимальные компоненты векторов
и
соответственно;
sx,
sy
- средние
значения компонент векторов
и
соответственно.
Решение:
#include "stdafx.h"
#include <math.h>
float Mod_Otkl (float *a, int n) /* функция для нахождения максимального компонента и среднего значения в любом массиве */
{
float ma, sa, Da;
int i;
ma =-10000;
sa=0;
for (i =0;i<n;i++)
{
if (a[i]>ma) ma= a[i];
sa += a[i];
}
sa = sa/n;
Da= fabs(ma - sa);
return Da;
}
void main()
{ float X[10],Y[10];
int i;
float Dx, Dy, D;
printf("Bведитe массив X:\n");
for (i =0;i<8;i++)
scanf("%f",&X[i]);
printf("Bведитe массив Y:\n");
for (i =0;i<10;i++)
scanf("%f",&Y[i]);
Dx = Mod_Otkl(X, 8); //вызов функции Mod_Otkl для массива X
Dy = Mod_Otkl(Y,10); //вызов функции Mod_Otkl для массива Y
D = Dx/Dy;
printf("D=%f\n",D);
}
Задача 2
Даны две матрицы: А = {a i j }5x6 и В = {b i j}4x7.
Вычислить разность: С = КА - KB, где КА и KB - количество положительных элементов в матрицах А и В соответственно.
#include "stdafx.h"
int CP(float D[7][7], int m, int n) /* функция для подсчета количества положительных элементов в матрице */
{ int i, j, KD;
KD=0;
for (i=0;i<m;i++)
for (j=0;j<n;j++)
if (D[i][j]>0) KD ++;
return KD;
}
int main()
{
float A[7][7], B[7][7];
int i,j, C;
printf("Введите матрицу А\n");
for (i=0;i<5;i++)
for (j=0;j<6;j++)
scanf("%f",&A[i][j]);
printf("Введите матрицу B\n");
for (i=0;i<4;i++)
for (j=0;j<7;j++)
scanf("%f",&B[i][j]);
C= CP(A, 5,6)- CP(B, 4, 7);
printf("C=%d\n", C);
return 0;
}
Задача 3
На плоскости декартовыми координатами заданы 10 точек:
{x1,y1},{x2,y2}, ...,{х10,у10}.
Вывести полярные координаты точки, имеющей наибольший полярный радиус. Вычисление полярных координат одной точки оформить подпрограммой. Расчетные формулы для вычисления полярных координат следующие:
,
где а
и
b
- координаты
точки.
Решение:
#include "stdafx.h"
#include<math.h>
void PK(float a, float b, float *ro, float *fi) /* функция для расчета полярных координат точки */
{
*ro = sqrt(a*a + b*b);
*fi = atan(b/a);
}
int main()
{
float X[10], Y[10], R[10], F[10];
int i, n;
float max;
printf("Введите абсциссы 10 точек\n");
for (i=0;i<10;i++) scanf("%f",&X[i]);
printf(" Введите ординаты 10 точек\n");
for (i=0;i<10;i++) scanf("%f",&Y[i]);
max = 0;
for (i=0;i<10;i++)
{
PK(X[i],Y[i],&R[i],&F[i]);
if (R[i]>max) // поиск максимального радиуса
{
max =R[i];
n=i;
}
}
printf("romax=%f fimax=%f\n", R[n],F[n]);
return 0;
}
Задача 4
Для заданных квадратных матриц: A = {a i j}3x3 и В = {bi j}4х4 вычислить симметричные матрицы по правилу:
Решение:
#include "stdafx.h"
void SM(float Y[4][4], int n, float X[4][4])
{
int i,j;
for (i=0;i<n;i++)
for (j=i;j<n;j++)
{
X[i][j]=(Y[i][j] + Y[j][i])/2;
X[j][i] =X[i][j];
}
}
void main()
{
float A[4][4], B[4][4], C[4][4], D[4][4];
int i, j;
printf("Введите матрицу А\n");
for (i=0;i<3;i++)
for (j=0;j<3;j++) scanf("%f",&A[i][j]);
printf("Введите матрицу B\n");
for (i=0;i<4;i++)
for (j=0;j<4;j++) scanf("%f",&B[i][j]);
SM(A, 3,C);
SM(B, 4, D);
printf("Симметричная матрица С\n");
for (i=0;i<3;i++)
{for (j=0;j<3;j++) printf("%8.2f",C[i][j]);
printf("\n");
}
printf("Симметричная матрица D\n");
for (i=0;i<4;i++)
{for (j=0;j<4;j++) printf("%8.2f",D[i][j]);
printf("\n");
}
}