手动跟踪递归函数 [英] Manually trace recursive functions

问题描述

我在跟踪递归函数时遇到了一些困难.例如，以下面的字符串置换函数为例:

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

给定一个输入，说 "abcd" 并通过以下方式调用它:

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

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

我如何快速(通过手动跟踪，即没有调试器，假设您正在接受采访)找出此类函数的第 10 个输出?更一般地说，如何跟踪递归函数?

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?

推荐答案

只需在 cout << 上插入断点即可字符串<.并且，跳过休息九次.它可能看起来很脏，但我认为这很简单.

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)

继续.

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

当函数返回时，擦除最后一行并写入返回值.(你的函数返回void，所以我只写return")

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

您想跟踪 cout <<<字符串<，因此将标准输出写入另一篇论文会很有用.(如果代码复杂，你可能需要更多的纸张，比如变量映射".)

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".)

我的想法类似于计算机如何处理递归函数.在这种情况下，纸"充当堆栈，而我的大脑充当 CPU.

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

如果你把论文填得太紧，会抛出StackOverflowException.不过别担心.也许你有很多张纸！

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

这篇关于手动跟踪递归函数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！