递归算法求最长公共子序列问题，数据输入 两个子序列X和Y 数据输出 最长公共子序列和公共子序列长度C语言代码

递归算法求解最长公共子序列（LCS）的问题时，需要接收两个字符串作为输入，比如X和Y。这里是一个简单的C语言代码示例，使用递归方法实现：

#include <stdio.h>
#include <string.h>

// 用于存储中间结果的结构体
typedef struct {
    char* str; // 子序列
    int len; // 长度
} LCSNode;

// 辅助函数，返回给定位置i和j的子序列长度
int lcsLength(int i, int j, char* X, char* Y) {
    if (i == 0 || j == 0) // 基本情况，结束条件
        return 0;
    else if (X[i-1] == Y[j-1]) { // 当前字符相等，递归向前一步
        LCSNode temp;
        temp.str = &X[i-1];
        temp.len = 1 + lcsLength(i-1, j-1, X, Y);
        return temp.len;
    }
    else { // 否则取两边中较长的一个
        LCSNode left = {NULL, lcsLength(i-1, j, X, Y)};
        LCSNode right = {NULL, lcsLength(i, j-1, X, Y)};
        return left.len > right.len ? left.len : right.len;
    }
}

// 主函数，计算并打印最长公共子序列
void printLCS(char* X, char* Y) {
    int n = strlen(X), m = strlen(Y);
    LCSNode lcs = {NULL, lcsLength(n, m, X, Y)};
    char* lcsStr = malloc(lcs.len + 1); // 动态分配内存
    lcsStr[lcs.len] = '\0';

    // 回溯构造最长公共子序列
    int i = n, j = m;
    while (i > 0 && j > 0) {
        if (X[i-1] == Y[j-1]) {
            *(lcsStr + lcs.len - 1) = X[i-1]; // 将当前字符添加到结果中
            lcsStr--; // 移动指针
            i--;
            j--;
        } else if (lcs.left.len > lcs.right.len) {
            i--;
        } else {
            j--;
        }
    }

    printf("最长公共子序列为: %s\n", lcsStr);
    free(lcsStr); // 释放内存
}

// 测试函数
int main() {
    char X[] = "ABCBDAB";
    char Y[] = "BDCAB";
    printLCS(X, Y);
    return 0;
}

此代码首先定义了一个辅助函数`lcsLength`来递归地计算LCS长度，然后在主函数`printLCS`中构建最长公共子序列。注意，实际运行时应处理好内存管理，以免出现内存泄漏。