Лекция 5. Функции
#######################################################################################



Описание и использование функций
===========================================================


Функциональная декомпозиция
-----------------------------------------------------------



.. admonition::  Архитектура

   **Функция** - основной строительный элемент программы.

.. image:: _static/05/ris1.png


Функциональная модель программы
``````````````````````````````````````````````````````````

Рассмотрим функциональную модель программы с одним потоком выполнения. В один момент времени может выполняться только одна функция.


Выполнение программы начинается с **main**, а далее она передаёт управление другим функциям. 


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


С функцией обычно связывают две операции:


#. **Объявление** - определение функции с именем и параметрами 
#. **Вызов** - применение функции к некоторым данным


Стек вызовов
-----------------------------------------------------------

Для работы механизма вызова процедур используется **стек вызовов:**



.. image:: _static/05/CallStack.png


Объявления
-----------------------------------------------------------


Объявление функции
``````````````````````````````````````````````````````````

*Полное объявление (**описание*)** - может встречаться один раз.

*Неполное объявление (**прототип*)** - может встречаться много раз.

[<sc-specifier>]<type-specifier>name([type-specifier arg1,...);


Классы памяти и возвращаемое значение
``````````````````````````````````````````````````````````

.. admonition::  Классы памяти


* **extern** (по-умолчанию) - функция видна во всех файлах
* **static** - функция видна только в текущем файле
Возвращаемые значения:


* по-умолчанию - **int**
* при отсутствии - **void**


.. code-block:: c

 fun()
 {
    ...
    return N;
 }


  

         



.. code-block:: c

 void fun()
 {
     ...
 }



Организация однофайловой программы
``````````````````````````````````````````````````````````

.. admonition::  \textbf{main} в конце файла

   


.. code-block:: c

 fun1()
 {
 }
 fun2()
 {
     fun1();
 }
 main()
 {
     fun1();
     fun2();
 }


.. admonition::  Промежуточный вариант



.. code-block:: c

 fun2();
 fun1()
 {
     fun2();
 }
 fun2()
 {
 }
 main()
 {
     fun1();
     fun2();
 }


.. admonition::  \textbf{main} в начале



.. code-block:: c

 fun1();
 fun2();
 main()
 {
     fun1();
     fun2();
 }
 fun1()
 {
 }
 fun2()
 {
 }



Организация многофайловой программы
``````````````````````````````````````````````````````````

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


#. Описывать функции как **extern** (по-умолчанию).
#. Помещать в начало файла, где функция вызывается, **прототип**.




.. code-block:: c

 /* File1.c */
 int fun()
 {
 }




.. code-block:: c

 /* File2.c */
 int fun(); // прототип!
 int main()
 {
     int val=fun();
     return 0;
 }



Параметры функций
===========================================================


Виды параметров
-----------------------------------------------------------


Формальные и фактические параметры
``````````````````````````````````````````````````````````



При описании функции мы указываем **формальные** параметры



.. code-block:: c

 int  fun (char a1, int a2, float* a3)


При вызове функции мы указываем **фактические параметры**



.. code-block:: c

 int r = fun ('#', 256, &val)


Фактические параметры должны соответствовать формальным!


И снова стек вызовов
``````````````````````````````````````````````````````````


.. image:: _static/05/CallStackFrame.png


Некорректная программа
``````````````````````````````````````````````````````````

.. admonition::  Что напечатает программа?



.. code-block:: c

 
 int fa() { puts("fa"); return 1;}
 int fb() { puts("fb"); return 2;}
 int fc() { puts("fc"); return 3;}
 
 void fun( int a, int b, int c)
 {
     printf("%d %d %d",a,b,c);
 }
 int main()
 {
     fun(fa(),fb(),fc());
     return 0;
 }



Неккоректная программа
``````````````````````````````````````````````````````````

Неккоректной программы происходит из-за неопределённого в языке порядка вычисления аргументов функции. Поэтому в разных системах строки **fa,fb,fc** могут появляться на экране в разном порядке.


Передача параметров
-----------------------------------------------------------


Способы передачи параметров
``````````````````````````````````````````````````````````



*По значению* 

(by value)




.. code-block:: c

 void fun(short value)
 {
     value++;
 }
 int main()
 {
     short value=14;
     fun(value);
     printf("%d", value);
     return 0;
 }


Содержимое стека


.. image:: _static/05/ris2.png



*По указателю* 

(by pointer)




.. code-block:: c

 void fun(short *value)
 {
     (*value)++;
 }
 int main()
 {
     short value=14;
     fun(&value);
     printf("%d", value);
     return 0;
 }


Содержимое стека


.. image:: _static/05/ris3.png

В языке С++ предложен третий способ: **по ссылке (by reference)**




.. code-block:: c

 void fun(short& value)
 {
     value++;
 }
 int main()
 {
     short value=14;
     fun(value);
     printf("%d", value);
     return 0;
 }



Передача массивов
``````````````````````````````````````````````````````````

Массивы передаются только по указателю!



.. code-block:: c

 // передаём адрес массива и число элементов
 int getSum(int *arr,int size)
 {
     int sum=0;
     for(int i=0;i<size;i++)
        sum+=arr[i];
     return sum;
 }




.. code-block:: c

 int main()
 {
     int arr[]={1,2,3,4,5};
     int sum=0,size=5;
     sum=getSum(arr,size);
     return 0;
 }


А вот так передаются *двумерные* массивы



.. code-block:: c

 int getSum2(int (*arr)[M],
             int N)
 {
     int i,j,sum=0;
     for(i=0;i<N;i++)
        for(j=0;j<M;j++)
          sum+=arr[i][j];
    return sum;
 }




.. code-block:: c

 int main()
 {
     int arr[][M]={{1,2},
                   {3,4},
                   {5,6}};
     int sum=0,N=3;
     sum=getSum2(arr,N);
     return 0;
 }



Командная строка
===========================================================


Работа с командной строкой
``````````````````````````````````````````````````````````

Запуск программы без параметров



.. code-block:: none

 C:\Programs\>myprog.exe


Запуск программы с параметрами



.. code-block:: none

 C:\Programs\>myprog.exe  param1  param2  param3


Способы передачи данных в программу
``````````````````````````````````````````````````````````

Данные могут появляться в программе:


#. В виде констант (присутствие в коде).
#. Поступать с клавиатуры в режиме диалога.
#. Поступать из файлов данных.
#. Поступать с др. устройств (например, сеть).
#. **Поступать через командную строку**


Параметры **main**
``````````````````````````````````````````````````````````



.. admonition::  Варианты заголовка main

   


.. code-block:: c

 int main(int argc, char *argv[ ])  
 int main(int argc, char **argv)


**argc** – переменная, содержащая число слов в ком. строке

**argv** – массив указателей на первые символы каждого слова

%\begin{lstlisting}

%filecopy 1.txt 2.txt

%\end{lstlisting}


.. image:: _static/05/ris5.png


Программа печати приветствия
``````````````````````````````````````````````````````````



.. code-block:: c

 int main(int argc, char *argv[])
 {
    if(argc<2)
    {
        printf("Usage: cmd_hello number");
        return 1;
    }
    int number=atoi(argv[1]);
    for(int i=0;i<number;i++)
       printf("%03d - %s\n", i+1,"Hello!");
    return 0;
 }



Рекурсия
===========================================================


Понятие рекурсии
-----------------------------------------------------------

.. admonition::  О понимании рекурсии

    *Чтобы понять рекурсию нужно...понять рекурсию.* 
.. admonition::  Из словаря:

    **Рекурсия** - см. *рекурсия* 

.. admonition::  Цитата

      Итерация от человека. Рекурсия - от Бога.- Л. Питер Дойч 
      ``(Д. Кнут. Искусство программирования.)``

.. image:: _static/05/recur1.png


.. image:: _static/05/recur2.png


.. image:: _static/05/fract1.png

.. admonition::  Рекурсивный подход к решению задач

   Разбиение задачи на более простые подобные задачи
.. admonition::  Рекурсивный объект

   Объект называется рекурсивным, если он определен с помощью ссылки на самого себя *GNU=GNU is Not Unix*.
.. admonition::  Рекурсивная процедура

   Если процедура  :math:`p`  содержит явное обращение к самой себе, то она называется явно рекурсивной. Если процедура  :math:`р`  содержит обращение к некоторой процедуре  :math:`q` , которая в свою очередь содержит прямое или косвенное обращение к  :math:`p` , то  :math:`p`  - называется косвенно рекурсивной.
\underline{Прямая рекурсия



.. code-block:: c

 void fun()
 {
   ...
   fun();
 }


*Косвенная рекурсия*



.. code-block:: c

 void fun1()
 {
    ...
    fun2();
 }
 void fun2()
 {
    ...
    fun1();
 }



Задачи
-----------------------------------------------------------


Рекурсивные задачи
``````````````````````````````````````````````````````````

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


#. Сумма элементов массива равна сумме сумм элементов его подмассивов.
#. Нахождение максимального элемента массива является результатом сравнения первого элемента с максимальным элементом оставшейся части массива.

Использование рекурсии для решения этих задач не всегда эффективно.

Существуют специальные задачи, решаемые обычно с помощью рекурсии:


#. Вычисление факториала целого числа.
#. Вычисление чисел Фибоначчи.
#. Решение головоломки "Ханойские башни".
#. Генерация фракталов.


О бесконечности и рекурсии
``````````````````````````````````````````````````````````

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


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


Алгоритм построения рекурсивной функции
``````````````````````````````````````````````````````````


* Разработать заголовок рекурсивной функции
* Определить терминальное условие (условие возвращения)
* Определить связь текущей копии функции с результатом вызова себя самой

.. image:: _static/05/ris6.png


.. image:: _static/05/ris7.png


Примеры
``````````````````````````````````````````````````````````

.. admonition::  Вычисление факториала



.. code-block:: c

 int factorial(int N)
 {
    if(N<=1)
       return 1;
    else
       return N*factorial(N-1);
 } 


.. admonition::  Числа Фибоначчи



.. code-block:: c

 int fib(int N)
 {
    if(N==1 || N==2)
       return 1;
    else
       return fib(N-1)+fib(N-2);
 } 



Вычисление факториала
``````````````````````````````````````````````````````````



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


**ЛРП** могут приводить к сбоям в работе программ из-за исчерпания свободной памяти.


Числа Фибоначчи
``````````````````````````````````````````````````````````

Пример N2 показывает, как можно найти n-ое число Фибоначчи.


Рассмотрим числовой ряд:


.. code-block:: none

 1,1,2,3,5,8,13,21....

Первые два члена ряда равны 1, а потом значение последующего равно сумме двух предыдущих.


.. code-block:: none

 fib(n) = 1, n = 1
 fib(n) = 1, n = 2
 fib(n) = fib(n-1) + fib(n-2), n > 2

Данная программа демонстрирует использование **древовидной рекурсии**, поскольку количество вычислений растёт экспоненциально из-за ветвлений при каждом вызове **fib**.


Древовидная рекурсия с ростом **n** может приводить к огромным вычислительным затратам, если одно и то же значение вычисляется множество раз.

Изображение древовидного рекурсивного процесса (ДРП):


.. image:: _static/05/fib-tree.png


Числа Фибоначчи (экономный вариант)
``````````````````````````````````````````````````````````



.. code-block:: c

 typedef unsigned long long ULL;
 ULL fib_iter(ULL K, ULL M, int N)
 {
    if(N==1)
       return M;
    else
       return fib_iter(M,K+M,N-1);
 }
 ULL fib(int i)
 {
    return fib_iter(0,1,i);
 }
 int main()
 {
    int i;
    for(i=1;i<=70;i++)
       printf("%d-%lld\n",i,fib(i));
    return 0;
 }



Числа Фибоначчи
``````````````````````````````````````````````````````````

В приведённом примере рекурсия может быть представлена в виде *итерации* без линейного расширения объёма используемой памяти и может быть заменена обычном циклом. 


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



Ханойские башни
-----------------------------------------------------------

.. admonition::  Задача

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

.. admonition::  Решение

   Нужно применить рекурсивно алгоритм, переложив  :math:`n-1`  кольцо с первой пирамиды на третью пирамиду. Затем сделать очевидный ход, переложив последнее самое большое кольцо с первой пирамиды на вторую. Затем снова применить рекурсию, переложив  :math:`n-1`  кольцо с третьей пирамиды на вторую пирамиду. 

.. image:: _static/05/han1.png


Ханойские башни (реализация)
``````````````````````````````````````````````````````````

{\small



.. code-block:: c

 void han(int num,char a,char b,char c) {
    if(num>0)   {
       han(num-1,a,c,b);
       printf("%c--->%c\n",a,c);
       han(num-1,b,a,c);
     }
 }
 int main() {
   char a,b,c;
   int num;
   printf("Enter number of rings: ");
   scanf("%d",&num);
 
   a='A';b='B';c='C';
   if(num>0)
     han(num,a,b,c);
   else
     puts("Error!");
   return 0;
 }


}


Дополнительная информация
===========================================================


Указатели и функции
``````````````````````````````````````````````````````````

При передаче адресов в функции могут возникать трудноуловимые ошибки:



.. code-block:: c

 void fun(int **p)
 {
    int val=10;
    *p=&val;
 }
 int main()
 {
    int *p;
    fun(&p);
    (*p)++; // Ошибка!
 }


В приведённом примере мы присваиваем внешнему указателю адрес локальной переменной **val**, которая будет уничтожена после возвращения из **fun**.


Вопросы для самоконтроля
=============================================

  * Что такое функциональная декомпозиция?

  * Как описывает программу функциональная модель?

  * Что такое многопоточная программа?

  * Какие операции характерны для функции?

  * Что такое описание функции?

  * Что такое прототип?

  * Какие классы памяти могут использоваться при описании функции?

  * Что возвращает функция, если не указывать явно тип возвращаемого значения?

  * Как организуются функции в одно-файловой программе?

  * Как организовать многофайловую программу с функциями?

  * В чем отличие между фактическими и формальными параметрами функции?

  * Почему опасно полагаться на последовательность обработки параметров функции?

  * Как параметр передается по значению? Когда используется такой способ передачи параметров?

  * Как передается параметр через указатель? Когда используется такой способ передачи параметров?

  * Как осуществляется передача массива в функцию?

  * Как передать в функцию двумерный массив?

  * Как запустить программу с параметрами?

  * Как могут поступать данные в программу?

  * Как описывается заголовок main при передаче ей параметров из командной строки?

  * Что означают параметры main?

  * Что такое рекурсивная функция?

  * Какие существуют разновидности рекурсии?

  * Опишите алгоритм построения рекурсивной функции?

  * Как рекурсивно реализовать вычисление факториала? Чисел Фибоначчи?

  * Что такое линейный рекурсивный процесс?

  * Чем опасен ЛРП?

  * Как образуется ряд Фибоначчи?

  * Как можно реализовать процедуру получения ряда Фибоначчи?

  * Что такое древовидная рекурсия?

  * Чем опасна древовидная рекурсия?

  * Как можно представить древовидный рекурсивный процесс?

  * Что такое хвостовая рекурсия?

  * Чем полезна хвостовая рекурсия?