Рубрики

Практические вопросы для рекурсии | Набор 7

Вопрос 1 Предсказать результаты следующей программы. Что вообще делает следующее fun ()?

#include <stdio.h>

  

int fun ( int n, int *fp )

{

    int t, f;

  

    if ( n <= 1 )

    {

        *fp = 1;

        return 1;

    }

    t = fun ( n-1, fp );

    f = t + *fp;

    *fp = t;

    return f;

}

  

int main()

{

    int x = 15;

    printf("%d\n",fun(5, &x));

  

    return 0;

}

Выход:

8 

Программа рассчитывает n-е число Фибоначчи. Оператор t = fun (n-1, fp) дает (n-1) -ое число Фибоначчи, а * fp используется для хранения (n-2) -го числа Фибоначчи. Начальное значение * fp (которое в указанной выше программе равно 15) не имеет значения. Следующее дерево рекурсии показывает все шаги от 1 до 10 для исполнения fun (5, & x).

                              (1) fun(5, fp)
                              /           \
                         (2) fun(4, fp)  (10) t = 5, f = 8, *fp = 5
                         /          \
                   (3) fun(3, fp)  (9) t = 3, f = 5, *fp = 3
                  /            \
           (4) fun(2, fp)      (8) t = 2, f = 3, *fp = 2
          /          \
   (5) fun(1, fp)   (7) t = 1, f = 2, *fp = 1
   /
(6) *fp = 1

Вопрос 2: Предсказать результаты следующей программы.

#include <stdio.h>

  

void fun(int n)

{

    if(n > 0)

    {

        fun(n-1);

        printf("%d ", n);

        fun(n-1);

    }

}

  

int main()

{

    fun(4);

    return 0;

}

Выход

1 2 1 3 1 2 1 4 1 2 1 3 1 2 1
                     fun(4)
                   /
                fun(3), print(4), fun(3) [fun(3) prints 1 2 1 3 1 2 1]
               /
           fun(2), print(3), fun(2) [fun(2) prints 1 2 1]
           /
       fun(1), print(2), fun(1) [fun(1) prints 1]
       /
    fun(0), print(1), fun(0) [fun(0) does nothing]

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

Рекомендуемые посты:

Практические вопросы для рекурсии | Набор 7

0.00 (0%) 0 votes