Suppose a string s of size n is given. Now you have to answer the minimum number of characters to append at the end to make it a palindrome. How to solve this problem in O(n) time complexity?

As a beginner, I face lots of difficulties thinking a program recursively. After thinking for a while, I can tell the output of a recursive function but when I try to write a program recursively on my own, my head gets messy and I can't think properly after some time. I want to know how to think a program recursively in an intuitive way so that I can write a recursive program without thinking recursive tree or call stack every time. How do you think when you write a complex recursive solution?