Функции

Прототипы функций

 

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

 

 

// определение максимального из трех целых чисел

 

#include "stdafx.h"

#include <iostream>

 

using namespace std;

 

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

 

int _tmain(int argc, _TCHAR* argv[])

{

setlocale(LC_ALL, "rus");

int a, b, c;

 

cout <<"Введите три целых числа: ";

cin >>a >>b >>c;

cout <<"Maximum равен " <<maximum(a,b,c)<<endl;

return 0;

}

// определение функции maximum

int maximum(int x, int y, int z)

{

int max=x;

 

if (y>max)

max=y;

if (z>max)

max=z;

 

return max;

}

 

 

Рекурсия.

Рекурсивная функция — это функция, которая вы­зывает сама себя либо непосредственно, либо косвенно с помощью другой функции.

Рекурсивная задача в общем случае разбивается на ряд этапов. Для решения задачи вызывается рекурсивная функция. Эта функция знает, как решать только простейшую часть задачи — так называемую базовую задачу (или несколько таких задач). Если эта функция вызывается для решения базовой задачи, она просто воз­вращает результат. Если функция вызывается для решения более сложной задачи, она делит эту задачу на две части: одну часть, которую функция умеет решать, и другую, которую функция решать не умеет. Чтобы сделать рекурсию выполнимой, последняя часть должна быть похожа на исходную задачу, но быть по сравнению с ней несколько проще или несколько меньше. Так как эта новая задача подобна исходной, функция вызывает новую копию самой себя, чтобы начать работать над меньшей проблемой — это называется рекурсивным вызовом, или шагом рекурсии. Шаг рекурсии вклю­чает ключевое слово return,так как в дальнейшем его результат будет объ­единен с той частью задачи, которую функция умеет решать, и сформируется конечный результат, который будет передан обратно в исходное место вызова, возможно, в main.

Шаг рекурсии выполняется до тех пор, пока исходное обращение к функ­ции не закрыто, т.е. пока еще не закончено выполнение функции.

Шаг ре­курсии может приводить к большому числу таких рекурсивных вызовов, поскольку функция продолжает деление каждой новой подзадачи на две части. Чтобы завершить процесс рекурсии, каждый раз, как функции вы­зывает саму себя с несколько упрощенной версией исходной задачи, должна формироваться последовательность все меньших и меньших задач, в конце концов, сходящаяся к базовой задаче. В этот момент функция распознает базовую задачу, возвращает результат предыдущей копии функции, и после­довательность возвратов повторяет весь путь назад, пока не дойдет до пер­воначального вызова и не возвратит конечный результат в функцию main.

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

 

Факториал целого числа, number,большего или равного 0, может быть вычислен итеративно (нерекурсивно) с помощью оператора for следующим образом:

factorial = 1;

for (int counter = number; counter >=1; counter--)

factorial *=counter;

 

 


 

 

Вычисление 5! должно происходить в соответствии с рис. 3.13, Рис. 3.1З (а) показывает, как протекает последовательность рекурсивных вызовов до тех пор, пока не будет вычислен 1! = 1, что приведет к завершению рекурсии. Рис. 3.13(6) показывает значения, возвращаемые из каждого рекурсивного вызова оператору вызова до тех пор, пока не будет вычислено и возвращено окончательное значение.