В предложении template можно определить более одного родового типа данных, если использовать список с разделяющими запятыми. Например, приведенная ниже программа создает шаблонную функцию, использующую два родовых типа:
// demoTemplate.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <iostream>
using namespace std;
template <typename Typel, typename Type2>
void myfunc(Typel x, Type2 y);
int main(){
myfunc(10, "hi");
myfunc(0.23, 10L);
return 0;
}
template <typename Typel, typename Type2>
void myfunc(Typel x, Type2 y)
{
cout << x << ' ' << y << '\n';
}
В этом примере условные имена типов Typel и Туре2 заменяются компилятором на типы данных int и char*, а также double и longсоответственно, когда компилятор создает специфические экземпляры функции myfunc() в main().
Последняя тема, которую мы рассмотрим в этом модуле, посвящена рекурсии. Рекурсия, иногда называемая циклическим определением, представляет собой процесс определения чего-то с помощью самого себя. В приложении к программированию рекурсия — это процесс вызова функцией самой себя. Функцию, которая вызывает саму себя, называют рекурсивной.
Классическим примером рекурсии может служить функция factr(), которая вычисляет факториал целого числа. Факториалом числа N называют произведение всех целых чисел между 1 и N.. Например, факториал числа 3 (или, как говорят, "три факториал") вычисляется как 1x2x3, что равно 6. Ниже приведены как функция factr(), так и ее итеративный эквивалент.
Действие нерекурсивного варианта fact() вполне очевидно. Он использует цикл, начинающийся с 1, в котором каждое следующее число умножается на последовательно увеличивающееся пpоизведение.
Действие рекурсивной функции factr( ) несколько сложнее. При вызове factr( ) с аргументом 1 функция возвращает 1; в противном случае она возвращает произведение factr(n-l)*n. Для вычисления этого выражения factr( ) вызывается с аргументом (n-1). Это происходит до тех пор, пока n не станет равным 1, и вызов функции приведет к возврату из нее. Например, когда вычисляется факториал 2, первый вызов factr( ) породит второй вызов с аргументом 1. Этот вызов вернет 1, которая умножится на 2 (первоначальное значение n). Переменная answer будет тогда равна 2. Вы можете ради любопытства включить в factr( ) предложения cout, которые покажут, на каком уровне находится вызов и каков промежуточный результат (переменная answer).
Когда функция вызывает саму себя, для новых локальных переменных и параметров выделяется память (обычно на системном стеке), и код функции выполняется с самого начала с использованием этих новых переменных. Рекурсивный вызов не создает новой копии функции; только ее аргументы будут новыми. При возврате из каждого рекурсивного вызова старые локальные переменные и параметры удаляются из стека, и выполнение продолжается с точки вызова функции изнутри функции. Можно сказать, что рекурсивные функции действуют подобно раздвижной подзорной трубе, сначала раскладываясь, а затем складываясь.
Имейте в виду, что большинство рекурсивных функций не уменьшают размер кода в заметной степени. Кроме того, рекурсивные варианты большинства алгоритмов выполняются несколько более медленно, чем их итеративные эквиваленты, из-за добавления издержек на дополнительные функциональные вызовы. Слишком много рекурсивных обращений к функции может вызвать переполнение стека. Из-за того, что параметры и локальные переменные функции размещаются на стеке, и каждый новый вызов создает новую копию этих переменных, стек может истощиться. Если это произойдет, то могут быть разрушены другие данные. Реально, однако, вряд ли вам придется столкнуться с такой ситуацией, если только рекурсивная функция не зациклится.
Основное преимущество рекурсивных функций заключается в том, что их можно использовать для создания вариантов некоторых алгоритмов, которые оказываются проще и нагляднее, чем их итеративные аналоги. Например, алгоритм быстрого упорядочения довольно затруднительно реализовать в виде итеративных вызовов. Некоторые задачи, особенно в области искусственного интеллекта, кажутся прямо приспособленными для рекурсивного решения.
Составляя рекурсивную функцию, вы должны где-то в ней включить условное предложение, например, if, чтобы заставить функцию осуществить возврат без выполнения рекурсивного вызова. Если вы пренебрежете таким условным предложением, то вызвав однажды эту функцию, вы никогда из нее не вернетесь. Это, довольно распространенная ошибка. Разрабатывая программы с рекурсивными функциями, не стесняйтесь включать в них предложения cout, которые позволят вам наблюдать, что происходит в программе, и аварийно завершить выполнение, если вы обнаруживаете ошибку.
Ниже приведен другой пример рекурсивной функции, названной reverse(). Она выводит на экран строку задом наперед.
// Вывод строки задом наперед посредством рекурсии.
#include <iostream>
using namespace std;
void reverse(char *s);
int main() {
char str[] = "это просто проверка";
reverse (str) ;
return 0;
}
// Вывод строки задом наперед,
void reverse(char *s)
{
if(*s)
reverse(s+1);
else
return;
cout << *s;
}
Функция reverse() прежде всего проверяет, не передан ли ей указатель на завершающий ноль строки. Если нет, то reverse( ) вызывает себя с передачей в качестве аргумента указателя на следующий символ строки. Когда наконец будет найден завершающий ноль, вызовы начинают "раскручиваться", и символы появляются на экране в обратном порядке.
Еще одно замечание. Понятие рекурсии часто оказывается сложным для начинающих. Не отчаивайтесь, если этот материал показался вам слишком запутанным. С течением времени вы освоите и его.
