Блог

Здесь у меня есть код о рекурсии из geeksforgeeks.com

 #include<stdio.h>
void fun(int x)
{
  if(x > 0)
  {
     fun(--x);
     printf("%dt", x);
     fun(--x);
  }
}
 
int main()
{
  int a = 4;
  fun(a);
  return 0;
}
 

Я сам действительно теряюсь, я не могу понять принцип работы этой функции. Насколько я знаю, во-первых, рекурсивный каждый вызов функции хранится в стеке и запускается после достижения базового варианта. Однако я не могу понять, как это работает после функции printf, которую вызывает второй вызов. Кто-нибудь может мне объяснить, пожалуйста? Я очень рад, если это так.
Заранее спасибо за ваш прекрасный вклад.

Переменная x в fun(x) является локальной, и первый вызов-x-1, второй-x-2

Рассмотрим простейший случай

 fun(1)
 

В результате вызывается fun(0) и fun(-1)

 fun(2)
 

Приводит к вызову fun(1) и fun(0), а поскольку 1 > 0, fun(1) также вызовет fun(0) и fun(-1), прежде чем fun(2) вызовет fun(0)

Вот частичный стек вызовов, с отступом в соответствии с тем, какая функция вызывает

 fun(4)
  fun(3)
    fun(2)
      fun(1)
        fun(0)
        print
        fun(-1)
      print
      fun(0)
    fun(1)
      fun(0)
      print
      fun(-1)
    print
    fun(0)
  fun(2)
...
      
 

Приведенная ниже подробная информация иллюстрирует глубину вызова с использованием отступов и показывает вызовы для fun и printf для иллюстрации последовательности выполнения и вывода на печать:

 Line 15: fun(4)                       --> depth 1 
    Line 6: x=3, fun(3)               --> depth 2
        Line 6: x=2, fun(2)           --> depth 3
            Line 6: x=1, fun(1)       --> depth 4
                Line 6: x=0, fun(0)   --> depth 5, do nothing amp; return
                Line 7: printf        --> "0"
                Line 8: x=-1, fun(-1) --> depth 5, do nothing amp; return
                Return                --> depth 3
            Line 7: printf            --> "1"
            Line 8: x=0, fun(0)       --> depth 4, do nothing amp; return
            Return                    --> depth 2
        Line 7: printf                --> "2"
        Line 8: x=1, fun(1)           --> depth 3
            Line 6: x=0, fun(0)       --> depth 4, do nothing amp; return
            Line 7: printf            --> "0"
            Line 8: x=-1, fun(-1)     --> depth 4, do nothing amp; return
            Return                    --> depth 2
    Line 7: printf                    --> "3"
    Line 8: x=2, fun(2)               --> depth 2
        Line 6: x=1, fun(1)           --> depth 3
            Line 6: x=0, fun(0)       --> depth 4, do nothing amp; return
            Line 7: printf            --> "0"
            Line 8: x=-1, fun(-1)     --> depth 4, do nothing amp; return
            Return                    --> depth 2
        Line 7: printf                --> "1"
        Line 8: x=0, fun(0)           --> depth 3, do nothing amp; return
        Return                        --> depth 1
    Return                            --> depth 0
 

Прежде всего, я рекомендую вам прочитать книгу о рекурсии, например, книги Розсы Питера или Даниэля Фридмана («Маленький интриган«), или лучше пройти какой-нибудь курс первого курса/mooc введения. После этого вы сможете изучать более продвинутые предметы.

У вас есть этот код:

 void fun(int x)
{
  if(x > 0)
  {
     fun(--x);
     printf("%dt", x);
     fun(--x);
  }
}
 

Предположим, вы называете забавой(4).

В этом случае у вас есть сигма-рекурсивный оператор (также называемый примитивной рекурсией). Для рекурсии нужны некоторые предельные случаи. В данном случае это простая линейная рекурсия только в том случае, если «счетчик достигает нулевого значения» (то же самое, что и в определении арифметики Пеано).

Если он достигнет 0, он завершен. В противном случае он вызывает сам себя с числом, уменьшенным на 1 по отношению к предельному регистру, и собирает еще 2 вызова:

  printf("%dt", x);
 fun(--x);
 

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

 void fun(int x)
{
  if(x > 0)
  {
     fun(--x);
     printf("%dt", x);
  }
}
 

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

Практически,

• он называет себя для f(4),
• тогда f(3),
• тогда f(2),
• тогда f(1),
• тогда f(0) является предельным случаем,
• затем он возвращается к набору printf из f(1) и ПЕЧАТАЕТ 1,
• затем он возвращается к набору printf из f(2) и ПЕЧАТАЕТ 2,
• затем он возвращается в сложенный printf из f(3) и ПЕЧАТАЕТ 3,
• затем он возвращается в сложенный printf из f(4) и ПЕЧАТАЕТ 4.