solom 13 апр 2010 в 01:43
О рекурсивных процедурах

7 мин
1.2K
Приветствую вас, Хабролюди!

Речь пойдёт о прелестях рекурсивных процедур.

Функция, как мы знаем, принимает аргументы и возвращает значение в зависимости от них. Она обычно имеет вид y = f(x1,...xn);
При этом она не должна совершать никаких побочных действий. Потому что в таком случае она будет называтья процедурой.
Процедура может иметь примерно такой вид:
Copy Source | Copy HTML
void someProc (x1,...xn)
{
doDomething1();
...
doSomethingN();
} 






То есть просто выполнить несколько шагов. Она может прекрасно обходиться как без аргументов, так и без возвращаемого значения.



Если в теле функции мы организовываем вызов её же самой (рекурсию), то как правило,

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



Набивший оскомину пример факториала, но необходимый для иллюстрации:



Copy Source | Copy HTML
int fac(n)
{
if(n == 0)
    return 1;
return n * fac(n-1);
} 






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



А что же нам может дать рекурсивная процедура? У неё есть очень хорошая особенность, а именно: пространство ДО вызова самой себя и ПОСЛЕ.

Причём то, что ПОСЛЕ, выполняется впервые именно в тот момент, когда встретилось условие выхода из рекурсии (в простом случае). 



Copy Source | Copy HTML
void recProc(....)
{
// вот тут делаем всё до рекурсивного вызова
recProc(...);
// а здесь - всё, что после выхода из рекурсии
} 






То есть рекурсивную процедуру можно сравнить с пружиной, которая сначала закручивается, а потом раскручивается в исходное положение. 

Проиллюстрируем на примере. Скажем, стоит задача распечатать числа от 0 до N не используя цикл.



Вот так выглядит процедура:



Copy Source | Copy HTML
void cnt(int i)
{
    if(i) {
        // printf("%d\n",i); // ДО вхождения
        cnt(i-1);
    }
    printf("%d\n",i); // ПОСЛЕ вхождений
} 






В ней обозначен выход — если i станет нулём. Каждый раз она вызывается с аргументом, уменьшенным на единицу. Как только она вызвалась с нулём, происходит печать i. И выход. Но выходит-то она пока сама в себя и на предыдущую итерацию.

В результате мы получим печать цифр от 0 до заданного аргумента. Пружина затянулась и распускается. Мы наблюдаем процесс роспуска как раз.



Если раскомментировать строчку ДО вхождения, а ПОСЛЕ закомментировать, то мы получим обратный счёт. Если раскомментировать всё, то получится палиндром. Сначала нисходящая последовательность (закручивание), а потом возрастающая (роспуск). 



Этой особенности можно найти и более полезное применение. Для примера рассмотрим задачу по переводу числа в строку. Способ состоит в том, что мы последовательно получаем цифры, из которых состоит число, преобразовываем их в знаки и из них уже составляем строчку.



К примеру, число 496 в десятичной системе раскладывается так:

496 % 10 (берём остаток от деления на основание) = 6

49 % 10 (делим то, что осталось от предыдущего деления) = 9

4 % 10 = 4



Способ имеет 2 недостатка: 

1. Мы получаем цифры с конца

2. Мы не знаем, какой длины число



Керниган и Ричи предложили вот такое решение:



Copy Source | Copy HTML
void itoa(int n, char s[])
{
    int i, sign;
 
    if ((sign = n) <  0) /* записываем знак */
        n = -n; /* делаем n положительным числом */
    i =  0;
    do { /* генерируем цифры в обратном порядке */
        s[i++] = n % 10 + '0'; /* берем следующую цифру */
    } while ((n /= 10) >  0); /* удаляем */
    if (sign < 0)
        s[i++] = '-';
    s[i] = '\0';
    reverse(s);
} 






То есть они выстраивают строчку задом наперёд, а потом, с помощью функции reverse, её переворачивают. Решение, что называется «в лоб» и оставляет вопросы.

К примеру, сколько памяти выделять под строчку. Хитрые отцы-основатели предпочли это обойти и писать данные в уже определённый массив. 

Да и переворачивать каждый строчку после преобразования — не комильфо. Потому как подобные вызовы весьма часты и это, несомненно, скажется на производительности.



Тут нам и приходит на помощь рекурсивная процедура. Она способна преобразовать 

10-тичные, 16-ричные, 2-ичные и 8-ричные числа в строковый вид.



Вот как она выглядит:



Copy Source | Copy HTML
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
 
#define DEC  0
#define OCT 1
#define HEX 2
#define BIN 3
 
char *uitoa(int a,int r);
 
int main()
{
    int num = 7654894;
    int e_num = 0x4E35FF;
    int b_num = 0b1110011;
    int o_num = 077432;
 
 
    printf("%s\n",uitoa(e_num,HEX));
    printf("%s\n",uitoa(b_num,BIN));
    printf("%s\n",uitoa(o_num,OCT));
}
 
 
 
 
char *uitoa(int a,int r)
{
/* Процедура принимает число и систему счисления <br/>*<br/>* инициализируются изначальна статические переменные<br/>* которые не будут сбрасываться на различных этапах рекурсии <br/>*/
    static int szmem =  0; // Размер памяти под строчку
    static char *mas =  0; // Указатель на начало памяти под строчку 
    static char *bgmas =  0; // То же самое
 
    char numb [] = "0123456789ABCDEF"; // Знаки 0 - это '0', 15 - 'F'
    int dig[] ={10,8,16,2}; // Основания 
 
    if(a == 0) {
        if(szmem == 0) {
 
// Это если аргументом был самый обыкновенный 0
// Выделяем 2 sizeof(char), кладём знак 0 и конец строки (просто 0)
 
            mas = malloc( 2 * sizeof(char) );
            assert(mas);
            *mas = '0';*(mas + 1) =  0;
 
            return mas; // Больше никаких действий
        }
 
/* Здесь мы оказываемся, когда szmem равен количеству байт<br/>* под строчку и при параметре a равным 0 (условие выхода)<br/>* Выделяем память szmem + sizeof(char) и ставим в конце 0<br/>* как завершение строки и выходим из рекурсии<br/>*/ 
 
    bgmas = mas = malloc( szmem * sizeof(char) + sizeof(char) );
    assert(mas);
 
    *(mas+szmem) = (char) 0;
 
    }else {
 
/* То самое место ДО входа. Пока ещё a!=0 Тупо увеличиваем <br/>* на единицу необходимое количество памяти и<br/>* делаем рекурсивный вызов с уменьшенным <br/>* параметром a<br/>*/
 
        szmem++;
        uitoa( a / dig[r],r );
 
/* То самое место ПОСЛЕ выхода из рекурсии<br/>* То есть мы на каждом этапе выхода, заполняем<br/>* с самого НАЧАЛА нашу строчку знаками,<br/>* начиная со СТАРШЕГО разряда. <br/>*<br/>* Помним: в это место мы приходим после того,<br/>* как "пружина" начала роспуск. А так как мы <br/>* на этапе "закручивания" входили с уменьшающимся<br/>* параметром, то тут он будет расти. <br/>*<br/>* Указатель<br/>* mas изменяется только здесь, потому что <br/>* объявлен как статический.<br/>*/
 
        *mas++ = numb [a % dig[r]];
    }
 
    szmem =  0;
    return bgmas;
} 






Процедура выделяет память и возвращает на неё указатель. Так что после получения строчки и по окончании работы с ней, следует выполнить освобождение памяти, воизбежание memory leak.



Надеюсь, кому-та статья будет полезной в деле понимания рекурсии.
Теги:
Хабы:
Чулан
О рекурсивных процедурах

Публикации

Истории

Ближайшие события
