实现Karatsuba乘法C++代码

下面是实现Karatsuba乘法的C++代码，其中使用了递归的方法：

#include <iostream>
#include <string>

using namespace std;

// 去除字符串前导0
void removeLeadingZeros(string& str) {
    int i = 0;
    while (i < str.size() && str[i] == '0') {
        i++;
    }
    str = str.substr(i);
    if (str.empty()) {
        str = "0";
    }
}

// Karatsuba乘法
string karatsuba(const string& num1, const string& num2) {
    int len1 = num1.size();
    int len2 = num2.size();
    if (len1 == 0 || len2 == 0) {
        return "0";
    }
    if (len1 == 1 || len2 == 1) {
        return to_string(stoi(num1) * stoi(num2));
    }
    int n = max(len1, len2);
    if (n % 2 != 0) {
        n++;
    }
    string x1 = num1.substr(0, len1 - n/2);
    string x0 = num1.substr(len1 - n/2);
    string y1 = num2.substr(0, len2 - n/2);
    string y0 = num2.substr(len2 - n/2);

    string z2 = karatsuba(x1, y1);
    string z0 = karatsuba(x0, y0);
    string z1 = karatsuba(to_string(stoi(x1) + stoi(x0)), to_string(stoi(y1) + stoi(y0))) - z2 - z0;

    string res = "0";
    res += z2 + string(n, '0');
    res += z1 + string(n/2, '0');
    res += z0;

    removeLeadingZeros(res);
    return res;
}

int main() {
    string num1 = "123456789";
    string num2 = "987654321";
    cout << karatsuba(num1, num2) << endl;
    return 0;
}

需要注意的是，在计算``z1``时，需要递归调用``karatsuba``函数，而最后的结果需要去除前导0。