🗊Презентация Соглашения, принятые для языка Си

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

Несмотря на то, что ни стандарт языка Си, ни компилятор формально не налагают никакого ограничения на количество рекурсивных обращений, тем не менее оно практически всегда существует для любых типов компьютеров, ибо каждый новый вызов требует дополнительной памяти из ресурса программного стека Если количество вызовов излишне велико, возникает переполнение сегмента стека и операционная система уже не может создать очередного экземпляра локальных объектов функции, что ведет, как правило, к аварийному завершению программы

В качестве примера реализации рекурсивного алгоритма рассмотрим функцию printd() , печатающую целое число в виде последовательности символов ASCII (т.е. цифр, образующих запись этого числа): В качестве примера реализации рекурсивного алгоритма рассмотрим функцию printd() , печатающую целое число в виде последовательности символов ASCII (т.е. цифр, образующих запись этого числа): void printd(int num) { int i; if (num < 0) { putchar('-'); num = -num; } if ((i = num/10) != 0) printd(i); putchar(num % 10 + '0') ; } Если значение переменной value равно 123, то в случае вызова void printd(value); эта функция дважды обратится сама к себе для печати цифр заданного числа

Классическим примером написания рекурсивной функции является вычисление факториала целого числа. Разумеется, эту задачу легко решить при помощи обычного цикла, но на этом простом примере наглядно видна идея рекурсивного алгоритма Классическим примером написания рекурсивной функции является вычисление факториала целого числа. Разумеется, эту задачу легко решить при помощи обычного цикла, но на этом простом примере наглядно видна идея рекурсивного алгоритма Текст такой функции достаточно прост: /* Рекурсивное вычисление n! */ int fact(int n) { if (n==0) return (1); else return(n*fact(n-1)); } Если обратиться к этой функции, например, так: int m; ... m = fact(5);//продолжение ниже

то, прежде чем получить значение 5!, функция должна вызвать самое себя как fact(4) , та, в свою очередь, вызывает fact(3) . Так будет продолжаться до вызова fact(0) . Лишь после этого вызова будет получено конкретное число (единица). Затем все пойдет в обратном порядке, и в конце концов мы получим результат от обращения fact(5) : 120 то, прежде чем получить значение 5!, функция должна вызвать самое себя как fact(4) , та, в свою очередь, вызывает fact(3) . Так будет продолжаться до вызова fact(0) . Лишь после этого вызова будет получено конкретное число (единица). Затем все пойдет в обратном порядке, и в конце концов мы получим результат от обращения fact(5) : 120 ¦ Порядок возвратов | Возвращаемое ¦ | значение ¦ return(1) | 1 ¦ return(1*0!) | 1 ¦ return(2*1!) | 2 ¦ return(3*2!) | 6 ¦ return(4*3!) | 24 ¦ return(5*4!) | 120