0

I have some difficulty in tracking recursive functions. For example, take the following function for string permutation as an example:

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]);
        }
    }
}

Given an input, say "abcd" and call it by:

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

How can I quickly (by manually tracking, i.e. without debugger, consider you're in a interview) find out, say, the 10th output of such function? More generally, how to trace a recursive function?

Improve this question
4
  • 1
    Run it through a debugger Commented Jan 20, 2014 at 9:14
  • 1
    I'd say the good ol' fashioned way of doing it with a pen and paper works the best :) Commented Jan 20, 2014 at 9:14
  • @DrYap I would like to see some suggestion on how to do it with pen and paper. Commented Jan 20, 2014 at 9:15
  • 1
    That'd be a very subjective answer (and this is a subjective question) then. Commented Jan 20, 2014 at 9:17

3 Answers 3

Reset to default
1

Just insert break point on cout << str << endl;. and, skip break nine times. It can look dirty, but I think it is simple.

With a pen and paper: I'll write the parameters.

("abcd", 0, 3)

Then, make program run through my brain until recursive call. At that time, I write parameters again.

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

Go ahead.

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

When function returns, erase the last line and write the return value. (Your function returns void, so I write just "return")

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

And go ahead. When program recursive-calls or returns again, erase the last "return" mark and write there.

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

You want to trace cout << str << endl;, so it can be useful to write standard-output to another paper. (and you can need more paper if code is complicated, such as "variables map".)

My idea resembles how computer processes recursive function. In this case, the "paper" serves as stack, and my brain serves as CPU.

If you fill your paper tightly, StackOverflowException will be thrown. But don't worry. Maybe you have many sheets of paper!

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

Again, this is how to use debugger to help you. I would like to see suggestions on how to do it using pen and paper. Consider you are in a interview.
@herohuyongtao with pen and paper? Is your question to trace this function without computer, only man's thought?
1

Add an iteration count to the method call and then debug on the 10th call (or whatever you want):

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]);
        }
    }
}

You call the method using:

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

3 Comments

This is how to use debugger to help you. I would like to see suggestions on how to do it using pen and paper. Consider you are in a interview.
Then the answer is "use your brain" together with said pen & paper.
Any suggestion on how to do this?
1

Actually there is no fix rule to debug to recursive function which suit to all pattern although there is some way you could trace it out..please follow this link for more detail..

other then that you can use print statement to find out the value at each recursion.

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.