algorithm - 如何从递归算法中找到递归关系

Question

我知道如何从简单的递归算法中找到递归关系。

For e.g. 
QuickSort(A,LB, UB){
    key = A[LB]
    i = LB
    j = UB + 1
    do{
        do{
            i = i + 1
        }while(A[i] < key)
        do{
            j = j - 1
        }while(A[j] > key)
    if(i < j){
        swap(A[i]<->A[j])
    }while(i <= j)
    swap(key<->A[j]
    QuickSort(A,LB,J-1)
    QuickSort(A,J+1,UB)
}

T(n) = T(n - a) + T(a) + n

在上面的递归算法中，很容易理解每​​次递归调用后输入大小是如何减少的。但是如何找到一般算法的递归关系，它不是递归的，但也可能是迭代的。所以我开始学习如何将迭代算法转换为递归算法，以便更容易找到递归关系。我找到了这个链接 http://refactoring.com/catalog/replaceIterationWithRecursion.html .我曾经将我的线性搜索算法转换为递归算法。

LinearSearch(A,x,LB,UB){
    PTR = LB
    while(A[PTR]!=x && PTR<=UB){
        if(PTR==UB+1){
            print("Element does not exist")         
        }
        else{
            print("location"+PTR)
        }
    }
}

got converted to 

LinearSearch(A,x,LB,UB){
PTR=LB
print("Location"+search(A,PTR,UB,x))
}
search(A,PTR,UB,x){
   if(A[PTR]!=x && PTR<=UB){
        if(PTR==UB+1){
            return -1
        }
        else{
            return search(A,PTR+1,UB,x)
        }
    }
    else{
        return PTR
    } 
}

This gives the recurrence relation to be T(n) = T(n-1) + 1

但我想知道这是为任何算法寻找递归关系的正确方法吗？另外，我不知道如何为不止一个参数增加或减少的算法找到递归关系。

e.g.
unsigned greatest_common_divisor (const unsigned a, const unsigned b)
{
  if (a > b)
  {
    return greatest_common_divisor(a-b, b);
  }
  else if (b > a)
  {
    return greatest_common_divisor(a, b-a);
  }
  else // a == b
  {
    return a;
  }
}

Answer 1

首先，algorithms are very flexible所以你不应该期望有一个涵盖所有这些的简单规则。

也就是说，我认为对您有帮助的一件事是更多地关注您传递给算法的输入的结构，而不是算法本身。例如，考虑一下您在帖子中显示的 QuickSort。如果您看一眼那些嵌套的 do-while，您可能会猜测它的 O(N^2)，而实际上它是 O(N)。通过查看输入更容易找到真正的答案:i 总是增加，j 总是减少，当它们最终相遇时，数组的 N 个索引中的每一个都将恰好被访问一次。

Plus I don't know how to find recurrence relation for algorithms where more than one parameter is increasing or decreasing.

嗯，这些算法肯定比只有一个变量的算法更难。对于您用作示例的欧几里得算法，复杂度实际上是 not trivial找出并涉及考虑最大公约数，而不仅仅是查看算法实现的源代码。