На этом шаге рассмотрим понятие базового и рекурсивного случая.

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

 3 ... 2 ... 1

    Ее можно записать в рекурсивном виде:

int countdown(int  i) 
{ 
        cout << i << "..."; 
        countdown(i - 1); 
} 

    Введите этот код и выполните его. И тут возникает проблема: эта функция выполняется бесконечно!

 3 ... 2 ... 1 ... 0 ... -1 ... -2 ...

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

    Добавим базовый случай в функцию countdown:

int countdown(int  i) 
{ 
    if (i <= 1) 	← базовый случай 
    { 
        cout << 1; 
        return  0; 
    } 
    else  		← рекурсивный случай  
    { 
        cout << i << "..."; 
        countdown(i - 1); 
    } 
} 

    Теперь функция работает так, как было задумано. Это выглядит примерно так:

    Архив с примером на языке С++ можно взять здесь.

    Архив с примером на языке Pascal можно взять здесь.

    На следующем шаге продолжим рассматривать рекурсию.

Предыдущий шаг Содержание Следующий шаг