Assume $f$ decides a language $A$ in $O(g(n))$ time, where $n$ is the length of the input string. How to write a recursive algorithm to decide $A^*$ (recursive)?
Moreover, can an $O(n^2g(n))$ time algorithm be written to decide $A^*$ (dynamic programming)?
Yes, the dynamic programming portion is a hw assignment. CLRS book recommends using recursion first, then evolving to memoization, then the bottom-up approach. I can't even see how to write a recursive algorithm to solve this.