Блог

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

 void prnarray (int *arr, int nelem)
{
    if (--nelem > 0)                    /* wind-in (twice) until nelem == 0 */
        prnarray (arr, nelem);
    
    printf ("%dn", arr[nelem]);        /* unwind outputting elements */
}
  

(где nelem — количество элементов в массиве, технически не его «размер» [если это не массив char ])

Проследите, что произойдет, если эта функция была вызвана с:

 int main (void) {
    
    int arr[] = { 1, 2, 3 },
        nelem = sizeof arr/sizeof *arr;
    
    prnarray (arr, nelem);
}
  

Самый простой способ — просто создать таблицу со значением nelem . Например:

Извлечение

• nelem == 3 :

первоначальный вызов из main()

     prnarray (arr, nelem);
  

затем при первом вызове функции --nelem уменьшает значение nelem на 1 перед вычислением if() .

• nelem == 2 :

после if() инструкции путь выполнения:

     if (--nelem > 0)                    /* wind-in (twice) until nelem == 0 */
        prnarray (arr, nelem);
  

• nelem == 1 :

затем в следующем вызове после --nelem , nelem == 1 :

     if (--nelem > 0)                    /* wind-in (twice) until nelem == 0 */
        prnarray (arr, nelem);
  

• nelem == 0

затем при следующем вызове, последнем рекурсивном вызове, выполняется базовый вариант, потому что после --nelem , nelem == 0 поэтому условие теста не выполняется, и путь выполнения продолжается с:

     printf ("%dn", arr[nelem]);        /* unwind outputting elements */
  

(здесь печатается первый элемент ‘1’)

Разматывание

Что теперь происходит?? Мы достигли конца функции??

Выполнение начнется после вызова функции, которая приведет к этой точке. Где это?Вызов функции, который приводит к этой точке, является рекурсивным вызовом prnarray() , который приводит к тому, что мы находимся в теле этой функции.

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

• nelem == 1

Поэтому, когда выполнение функции where nelem == 0 заканчивается, мы возвращаемся к тому, на чем остановились в вызове функции where nelem == 1 — который возвращается из предыдущего вызова prnarray() , если мы посмотрим на всю функцию where nelem == 1 ( nelem == 2 при вводе функции), мы возвращаемся после предыдущего вызова на prnarray() один уровень вверх в recusrion:

 void prnarray (int *arr, int nelem)
{
    if (--nelem > 0)                    /* wind-in (twice) until nelem == 0 */
 <----- prnarray (arr, nelem);
|   
 -->printf ("%dn", arr[nelem]);        /* unwind outputting elements */
}
  

(здесь печатается второй элемент со значением 2 )

Таким образом, после предыдущего prnarray() развертывания в пути выполнения остается единственная команда printf() , и печатается второй элемент 2 , и функция завершается и снова разворачивается с тем же результатом:

• nelem == 2

( 3 при входе в функцию) путь выполнения — это printf() функция

     printf ("%dn", arr[nelem]);        /* unwind outputting elements */
  

(здесь печатается третий и последний элемент со значением 3 )

• nelem == 3

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

     prnarray (arr, nelem);
  

и программа завершается….

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

С помощью этой информации вы теперь сможете настроить свою функцию и знать, где искать результат, который будет иметь место. Дайте мне знать, если у вас возникнут дополнительные вопросы.

В вашем решении

• counter является локальной для функции и не влияет на рекурсивный вызов, поэтому все время печатается только первый элемент массива.
• при SIZE нулевом возврате вы возвращаете -1 ошибку компиляции.

Попробуйте передать адрес первого индекса массива примерно так, как показано ниже,

 void printArray(int arr[], int SIZE) 
{
   if (SIZE > 0) {
       printf("%d ", arr[0]);
       printArray(amp;arr[1], SIZE - 1);
    }
}
  

Вы могли бы перепроектировать ту же функцию, что и (обратите внимание на комментарии):

 // Signature -- array      size      parameterized counter
void printArray(int arr[], int SIZE, int counter) {
    if (SIZE == 0)
        // Quitting from the function instead of returning to a void function
        return;

    // Will print arr[0] on first recursion
    printf("%dn", arr[counter]);
    counter  ;

    // Will re-execute and print counter   (if it was 0, then 1, then 2, ...)
    printArray(arr, SIZE - 1, counter);
}