r是什么？算法是不是有点问题，百度百科里有好多，可以研究下。
递归调用还是比较好实现的，说白了就是一个辗转相除法。

可以证明两点：
1、x1与x2符号相反；
2、每次迭代，x1，x2符号均变反。

你给的程序只是计算公式的形式化，转化为C语言时需要做一些处理。简单的做法是添加一个标识x1符号的变量。

1. u = a; v = p;
2. x1 = 1; x2 = 0; flag=0;
3. 当 (u!=1) 时, 重复执行:

   3.1  q = v/u, r=v-qu, x = qx1+x2, x2=x1, x1=x;

   3.2  v = u, u = r, flag = flag^1;

4 if(flag==0) return x1%p;
else return (x1+p)%p;

这个程序可以改造成求最大公约数及其表达系数的程序：

x1=1,x2=0,y1=0,y2=1;flag = 0;
while(u)
        {
                q = v/u;
                r = v - q*u;               
                m = x2 + q*x1;
                n = y2 + q*y1;
                flag = flag^1;
               
                v = u;
                u = r;
                x2 = x1;
                x1 = m;
                y2 = y1;
                y1 = n;
        }        
        // ux + vy = d
        *d = v;// 最大公约数
        *x = x2;
        *y = y2;        
       
        return  flag;//返回x的符号位

这里使用递归是有风险的，栈消耗与初值相关，难以控制。

谢谢 publickey，

之所以不用递归 就是性能考虑。

上面给出的模逆运算错误, 无符号运算--有的结果对有的结果不对
===============

#include <stdlib.h>
#include <iostream>
using namespace std;

// 无符号运算模逆
unsigned long ModInv(unsigned long A, unsigned long P)
{
    unsigned long u = A, v = P;
    unsigned long x1 = 1, x2 = 0, flag=0;

    unsigned long q, r, x;
    while (u != 1)
    {
        q = v/u; r = v%u; x = q*x1 + x2;

        v = u; u = r; x2 = x1; x1 = x;

        flag = flag^1;
    }

    if (flag == 1) x1 += P;
    return x1%P;
};

// 有符号运算模逆
long long ModInv(long long A, long long P)
{
    long long u = A, v = P;
    long long x1 = 1, x2 = 0;

    long long q, r, x;
    while (u != 1)
    {
        q = v/u; r = v%u; x = x2 - (q*x1);

        v = u; u = r; x2 = x1; x1 = x;
    }

    x1 %= P;
    if (x1 < 0) x1 += P;
    return x1;
};

int main()
{
    cout << "Hello, world" << endl;

////////////////////

    // 65521是素数
    unsigned long x, a, p = 65521;
    long long X, A, P;

     //65521是2字节, a一定也小于2字节, a*a一定小于4字节, 不会溢出.
    for (unsigned i=0; i<20; i++)
    {
        a = rand();
        a %= p;
        A = a;
        P = p;

        cout << "计算: a=" << a << "  p=" << p << endl;
        X = ModInv(A, P);
        A *= X;
        A %= P;
        if (A == 1) cout << "有符号模逆运算成功: " << X << endl;
        else cout << "有符号模逆运算失败: " << X << "  **" << endl;

        x = ModInv(a, p);
        a *= x;
        a %= p;
        if (a == 1) cout << "无符号模逆运算成功: " << x << endl;
        else cout << "无符号模逆运算失败: " << x << "  **" << endl;

        cout << endl;
    }

    return 0;
};

//  x = x2 - (q*x1); 最麻烦的这步
//  如果x1和x2的符号不相等, 可以直接相加.
//  如果x1和x2的符号相等(同为负数或正数), 还要比较大小, 然后大的减小的, 差为正数.
//  希望有更简单的办法

最后一步错了。
if (flag == 1) x1 += P;
    return x1%P;

flag=1时，x1是负数，所以应该是p-x1

你没有理解这个运算，所以才会纠结符号。
这里不好编辑数学符号，难以讲清楚。