Ручная трассировка рекурсивных функций

Question

У меня есть некоторые трудности с отслеживанием рекурсивных функций. Например, возьмем следующую функцию для строки перестановки в качестве примера:

void string_permutation(string str, int mid, int end) 
{ 
    if (mid == end) 
     cout << str << endl; 
    else 
    { 
     for (int i = mid; i <= end; i++) 
     { 
      swap(str[mid], str[i]); 
      string_permutation(str, mid + 1, end); 
      swap(str[mid], str[i]); 
     } 
    } 
} 

Учитывая вход, скажем "abcd" и назвать его:

string str = "abcd"; 
string_permutation(str, 0, str.size()-1); 

Как я могу быстро (вручную отслеживать, т.е. без отладчик, подумайте, что вы в интервью) узнаете, скажем, 10-й результат такой функции? В более общем плане, как отслеживать рекурсивную функцию?

Answer 1

Просто вставьте разрыв точка на cout << str << endl;. и, пропустите перерыв девять раз. Это может выглядеть грязно, но я думаю, что это просто.

С ручкой и бумагой: Я напишу параметры.

("abcd", 0, 3) 

Затем, чтобы программа проходила через мой мозг до рекурсивного вызова. В это время я снова пишу параметры.

("abcd", 0, 3) 
("bacd", 1, 3) 

Вперед.

("abcd", 0, 3) 
("bacd", 1, 3) 
("bcad", 2, 3) 
("bcda", 3, 3) 

Когда функция возвращает, удалите последнюю строку и напишите возвращаемое значение. (Ваша функция возвращает пустоту, поэтому я пишу только «возврат»)

("abcd", 0, 3) 
("bacd", 1, 3) 
("bcad", 2, 3) 
return 

И вперед. Когда программа рекурсивна - вызовет или снова вернется, удалите последнюю метку «return» и напишите там.

("abcd", 0, 3) 
("bacd", 1, 3) 
return 

Вы хотите проследить cout << str << endl;, так что может быть полезно, чтобы написать стандартный-вывод в другой работе. (и вам может понадобиться больше бумаги, если код сложный, например «карта переменных».)

Моя идея напоминает, как компьютер обрабатывает рекурсивную функцию. В этом случае «бумага» служит как стек, а мой мозг - как процессор.

Если вы заполните плотно, StackOverflowException будет выброшен. Но не волнуйся. Возможно, у вас много листов бумаги!

Answer 2

Добавить итерационный счетчик для вызова метода, а затем отлаживать на 10-й вызов (или что вы хотите):

void string_permutation(string str, int mid, int end, int iterationCount) 
{ 
    // Bump up our iterationCount 
    iterationCount += 1; 

    // Debug on 10th call 
    if (iterationCount == 10) 
     Debug.WriteLine("10th call: " + str + ", " + mid + ", " + end); 

    if (mid == end) 
     cout << str << endl; 
    else 
    { 
     for (int i = mid; i <= end; i++) 
     { 
      swap(str[mid], str[i]); 
      string_permutation(str, mid + 1, end, iterationCount); 
      swap(str[mid], str[i]); 
     } 
    } 
} 

Вы вызываете метод с помощью:

string str = "abcd"; 
string_permutation(str, 0, str.size()-1, 0); 

Answer 3

На самом деле нет никакого правила исправления для отладки рекурсивной функции, которые подходят ко всему шаблону, хотя есть какой-то способ можно проследить его .. please follow this link for more detail..

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