возвращаемое значение рекурсивной функции

Question

Вывод приведенной ниже программы равен 24. Но я не мог понять поведение функции f1 (параметры).

В m1 и m2 существует рекурсивный вызов f1.Учитывая m1 и m2, удерживающие стек функции f1.Стек m1 будет содержать:

1]0,12,a 2]0,6,a 3]0,3,a 4]0,1,a 5]0,0,a

И стек m2 будет содержать:

1]13,12,a 2]20,6,a 3]24,3,a 4]26,1,a 5]27,0,a

Какие значения m1 и m2 сохраняются?пожалуйста, объясните это поведение рекурсивной функции.

#include <stdio.h>
main()
{
 int i, n, m, b, x[25];
 int f1(int, int, int j[25]);
 for(i=0;i<25;i++) x[i] = i;
 i=0; m = 24;
 b=f1(i, m, x);
 printf("res %d\n",b);
}

int f1( int p, int q, int a[25])
{
 int m1,m2;
 if (q==0)
  return(a[p]);
 else
 { 
  m1 = f1 (p, q/2, a);
  m2 = f1(p+q/2+1,q/2,a);
  if(m1<m2)
   return (m2);
  else
   return(m1);
 }
}

Answer 1

Ну, есть два момента для понимания кода:

1. Раскрытие фактического алгоритма среди кучи ужасных C и
2. понимание самой рекурсивной функции.

Когда я пытался понять такой код, мне всегда помогало:

1. Очистить код С. В данном случае это означает:

   1. Мысленно отслеживаем инициализацию и переписываем в статическую инициализацию, чтобы увидеть, как выглядят значения:

      int x [25] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24};

   2. Избавление от бесполезного назначения i и x, чтобы вы могли видеть начальный вызов на виду.

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

   f(p, q, array) = larger of f(p, q/2, array) and f(p+q/2+1, q/2, array)
   

   если вы продолжите немного использовать человеческий язык, вы ясно увидите, что должен был сделать .

Теперь я сказал "должен был сделать" специально. (p, q/2) и (p+q/2+1, q/2) выглядят как первая и вторая половина ... за исключением того, что это не так.

Код должен возвращать 24, но это совершенно неправильно, и стеки, указанные в вопросе, на самом деле доказывают это. Стек m2 содержит в качестве последней точки «f1 (27, 0, a)», и этот вызов будет выполнять a [27], но в массиве всего 25 элементов! (по чистой случайности вышеприведенная память, вероятно, была инициализирована 0, поэтому она возвращала 24, но если вместо этого она была инициализирована каким-либо шаблоном отладки (я видел 0xdeadbeef, 0xa5a5a5a5 и 0xcccccccc), она вернула бы это).

В C по замыслу (а C ++ использует их везде) проще всего использовать полуоткрытые интервалы. [start, one-past-end) или start + length, которые хорошо конвертируются. Однако здесь функция получает (start, length-1) и обрабатывает ее непоследовательно внутри.

Будучи студентом, вы должны быть в состоянии понять такой код, потому что вы встретите много дерьмового нечитаемого кода с ошибками, который работает в дикой природе только случайно. Но если ты когда-нибудь представишь что-то подобное, ты по праву провалишь экзамен.

Answer 2

Здесь вы не можете думать о стеке m1 и стеке m2 как о неразрывных вызовах f1, приводящих к рекурсивному вызову m1 и m2.

Чтобы проанализировать, что происходит, попробуйте для небольшого значения p и q.

   f1( 0, 1, a)
      m1 = f1( 0, 0, a); /* q/2 == 1/2 == 0 */
           /* q now 0 so return a[0] */
      m2 = f1( 1, 0, a);
           /* q now 0 so return a[1] */ 

   overall result the larger of a[0] and a[1].

Теперь попробуйте это для f1 (0, 2, a) и так далее, пока не увидите, что происходит.