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

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

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

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

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

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

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

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

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

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

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

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

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

Возвращаемые значения:

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

fun()
{
   ...
   return N;
}

void fun()
{
    ...
}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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)

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

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

По указателю

(by pointer)

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

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

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

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

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

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

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

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

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

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;
}

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

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

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

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

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

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

1. Вычисление факториала целого числа.
2. Вычисление чисел Фибоначчи.
3. Решение головоломки “Ханойские башни”.
4. Генерация фракталов.

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

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

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

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

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

Примеры¶

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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;
}

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

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

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

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

{small

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;
}

}