Как я могу анализировать рекурсивные исходные коды вручную?

Question

Как я могу анализировать рекурсивные исходные коды вручную?

Например, я разработал методику анализа итеративного исходного кода вручную, например:

int fact(int n) 
{ 
 int f = 0; 
 int i = 0; 
 if (n<=1)  
 {  
  return 1; 
 } 

 f = 1; 
 i = 2; 
 for (i=2; i<=n ; i++) 
 { 
  f *= i; 
 } 

 return f; 
}

---------------------------
  i         f       new-f
---------------------------
---------------------------
---------------------------

Для каждого 'i' я могу анализировать и вычислять значения old-f и new-f вручную и заполнять таблицу, чтобы увидеть, работает ли подпрограмма правильно.

Но как я могу анализировать рекурсивные процедуры вручную?

int fact(int number) {
    int temp;

    if(number <= 1) return 1;

    temp = number * fact(number - 1);
    return temp;
}

Answer 1

Поскольку рекурсия хранит значения в стеке, вам необходимо проанализировать ее в двух направлениях

1-й проход: выполнить рекурсию до достижения условия завершения.

2-й проход: собрать значенияпока стек не опустеет.

1st down  2nd up
---------------------------------
n = 6     tmp = 6 * 120 = 720 <- result
n = 5     tmp = 5 * 24 = 120
n = 4     tmp = 4 * 6 = 24
n = 3     tmp = 3 * 2 = 6
n = 2     tmp = 2 * 1 = 2
n = 1     end

Answer 2

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

Для факторного примера мы можемопределить факт как:

fact(x) = 1 when x <= 1
fact(x) = x * fact(x - 1) otherwise

Теперь, когда вы хотите выразить, как это работает, вы выбираете небольшое начальное число (скажем, 6) и ...

fact(6) = 6 * fact(5) = 6 * 5 * fact(4) = 6 * 5 * 4 * fact(3)

и т. д.on.

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

Answer 3

Вы можете использовать Отладчик, чтобы сделать это без изменения исходных кодов или написания новых кодов. 1. Установите точку останова по адресу функции с именем fact 2. Запустите отладчик, каждый раз, когда вы остановились на точке останова, вы можете проверить значение номера параметра и возвращаемое значение