Manually trace recursive functions [duplicate]

Question

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?

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

ikh · Accepted Answer · 2014-01-20 09:59:47Z

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!

edited Jan 20, 2014 at 9:59

answered Jan 20, 2014 at 9:17

ikh

10.5k2 gold badges36 silver badges77 bronze badges

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

2 Comments

herohuyongtao Over a year ago

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.

ikh Over a year ago

@herohuyongtao with pen and paper? Is your question to trace this function without computer, only man's thought?

robnick · Accepted Answer · 2014-01-20 09:15:15Z

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

answered Jan 20, 2014 at 9:15

robnick

1,76817 silver badges27 bronze badges

3 Comments

herohuyongtao Over a year ago

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.

robnick Over a year ago

Then the answer is "use your brain" together with said pen & paper.

herohuyongtao Over a year ago

Any suggestion on how to do this?

Community · Accepted Answer · 2017-05-23 12:28:37Z

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.

edited May 23, 2017 at 12:28

CommunityBot

11 silver badge

answered Jan 20, 2014 at 9:17

Ravindra Gupta

6083 gold badges9 silver badges18 bronze badges

Collectives™ on Stack Overflow

Manually trace recursive functions [duplicate]

3 Answers 3

2 Comments

3 Comments

Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

3 Comments

Comments

Linked

Related