With the growing adoption of microservice architectures in large-scale systems, efficient fault recovery has become critical for maintaining service availability and reliability. However, the dynamic dependencies, evolving service topologies, and resource constraints in microservices pose significant challenges to recovery decision-making. Existing methods—including rule-based, case-based, and model-based approaches—struggle with limited adaptability, insufficient dynamic modeling, and weak strategy generation capabilities, especially under complex failure scenarios. To address these challenges, we propose GRACE, a hybrid fault recovery framework that integrates dynamic graph modeling, reinforcement learning (RL), and large language model (LLM) optimization. GRACE models microservice dependencies and resource states as a dynamic graph, leveraging graph neural networks for real-time system representation. Based on this, an RL agent efficiently generates recovery strategies for routine failures, while the LLM module refines strategies for complex resource-related faults via contextual reasoning and parameter optimization. Extensive experiments in real-world microservice environments demonstrate that GRACE outperforms existing methods in both recovery efficiency and success rate, particularly in complex scenarios, providing an effective and scalable solution for intelligent fault recovery in modern microservice systems.