algorithm - 在没有计算机的情况下可视化和求解递归方程

Question

假设我有这样的事情:(预测输出)

void abc (char *s){

    if(s[0]=='\0')
        return;

    abc(s+1);
    abc(s+1);

    printf(“%c “, s[0]);
}

这题不难解，但我做题的时间太长了，而且我得重做2-3次这样的题，因为我忘记了递归和变量的值(尤其是有2-3个这样的递归语句)

遇到这样的问题，有什么好的方法可以使用吗？

Answer 1

基本技术是先从小输入开始。然后尝试使用更大的。然后尝试使用比这更大的一个。对于递归函数，应该会出现一种模式，让您可以在知道前一个函数的样子的情况下预测下一个函数的样子。

那么，让我们从一个空字符串开始。很简单，什么都不打印。

input: ""
output:

接下来是一个长度为1的字符串。几乎同样简单，两个递归调用都不做任何事情(空字符串情况)，然后打印字符串的字符。

input: "z"
output: z

接下来是一个长度为 2 的字符串。每个递归调用最终打印第二个字符(长度为 1 例的字符串)，然后打印第一个字符。

input: "yz"
output: zzy

那么，让我们尝试预测长度为 3 的字符串会发生什么情况。将发生的是排除第一个字符的子字符串被处理两次，然后打印第一个字符。该子字符串是长度为两种情况的字符串。所以:

input: "xyz"
output: zzyzzyx

那么，现在应该很清楚如何在给定当前输出序列的情况下导出下一个输出序列了。