c - 查找步骤以找到给定的索引值

Question

我是 SO 的新手 - 我有一个问题是在面试中被问到的，我一生都无法解决这个问题。我可以用 while/for 循环解决，但面试官特别要求不要使用它们我什至和我的几个 friend 讨论过，但无法解决。如果有人能指点一下。

问题是:对于给定的数组

s[] = {5,1,0,4,2,3}

1. 未给出数组长度。
2. 如果数组长度为5个内容保证在 0 到 5 之间。
3. 没有重复数。

样本长度(s, 3)- a[3] = 4 , a[4] = 2, a[2] = 0, a[0] = 5, a[5] =3 返回长度 4 。

对于给定的条件，编写子程序 int length (s, 3) - 求出找到给定值所需的步数 -

附加条件

1. 您不能使用任何循环语句，例如 for、while 等 -
2. 您不能使用任何全局或静态变量。
3. 您不能在该例程中调用其他例程
4. 您不能修改给定的函数参数 - 它只保持长度 (s, n)
5. 你也不能改变原始数组

Answer 1

另一种解决方案根本不修改数组，但在 x 的前 16 位中隐藏了一个额外的参数:

int length(int *s, int x){
    int start = (x >> 16) - 1;
    if (start < 0)
        start = x;
    if (s[x] == start)
       return 0;
    return 1 + length(s, ((start + 1) << 16) + s[x]);   
}

如果数组中的元素太多，这将失败，但我怀疑任何其他递归解决方案在任何情况下都可能在该点发生堆栈溢出。