In which of the following problems recurrence relation holds?

• A. Optimal substructure
• B. Tower of Hanoi
• C. Hallmark substitution
• D. Longest common subsequence