Функції у C можуть використовуватись рекурсивно; тобто, функція може викликати сама себе безпосередньо або опосередково. Розглянемо вивід числа як символьний ланцюжок. Як ми вказали раніше, цифри генеруються у неправильній послідовності: молодші числа доступні раніше за старші числа, хоча їх потрібно виводити навпаки.
Існує два способи розв'язання цієї проблеми. Одним буде збереження цифр у масив під час їхнього генерування, потім видрукувати їх у зворотній послідовності, як ми це здійснили з itoaу Розділі 3.6. Альтернативою є рекурсивне вирішення, у якому printd спочатку викликає себе щоби впоратись з початковими цифрами, після чого виводить кінцеві цифри. Майте на увазі, що ця версія може зазнати невдачі на найбільшому від'ємному числі.
#include <stdio.h>
/* printd: вивести n як десяткове */
void printd(int n)
{
if (n < 0) {
putchar('-');
n = -n;
}
if (n / 10)
printd(n / 10);
putchar(n % 10 + '0');
}
Під час виклику функцією самої себе рекурсивно, кожне звернення отримує свіжий набір усіх автоматичних змінних, незалежних від попередьного набору. Таким чином, у printd(123), перша printd отримує аргумент n = 123. Вона передає 12 другому printd, яка в свою чергу передає 1 третьому. printd третього рівня виводить 1 після чого повертається до printdдругого рівня, яка виводить 2, потім повертається до першого рівня. Він виводить 3 і завершується.
Інший хороший приклад рекурсії, це quicksort, алгоритм сортування, розроблений C.A.R. Hoare у 1962 році. Маючи масив, вибирається один елемент і решта розбиваєтся на дві групи — ті, що менші за вибраний елемент і ті, що більше або дорівнюють йому. Той самий процес потім застосовано рекурсивно до цих двох груп. Коли підгрупа залишилась з мешне ніж двома елементами, вона не потребує жодного сортування; це зупиняє рекурсію.
Наша версія quicksort не являється найшвидшою з можливих, але це одна з найпростіших. Ми використовуємо середній елемент кожної частини масиву для подальшого поділу.
/* qsort: сортує v[left]...v[right] у зростаючій послідовності */
void qsort(int v[], int left, int right)
{
int i, last;
void swap(int v[], int i, int j);
if (left >= right) /* нічого не робити, якщо масив */
return; /* містить менше ніж два елементи */
swap(v, left, (left + right)/2); /* перемістити елемент поділу */
last = left; /* до v[0] */
for (i = left + 1; i <= right; i++) /* поділити */
if (v[i] < v[left])
swap(v, ++last, i);
swap(v, left, last); /* відновити елемент поділу */
qsort(v, left, last-1);
qsort(v, last+1, right);
}
Ми перемістили операцію переставляння у окрему функцію swap, оскільки вона відбувається три рази у qsort.
/* swap: поміняти місцями v[i] і v[j] */
void swap(int v[], int i, int j)
{
int temp;
temp = v[i];
v[i] = v[j];
v[j] = temp;
}
Стандартна бібліотека включає власну версію qsort, спроможну сортувати об'єкти будь-якого типу. Рекурсія може займати місце, оскільки десь потрібно втримувати стек значень для обробки. Також вона не є швидшою. Але рекурсивний код компактніший і часто набагато простіший у написанні і розумінні, чим не-рекурсивний еквівалент. Рекурсія особливо зручна для рекурсивно-визначених даних на зразок деревовидних структур; ми побачимо гарний приклад цього у Розділі 6.6.
Вправа 4-12. Пристосуйте ідеї printd для написання рекурсивної версії itoa; тобто перетворіть ціле у ланцюжок, шляхом виклику рекурсивної функції.
Вправа 4-13. Напишіть рекурсивну версію функції reverse(s), яка обертає ланцюжок s на місці.
