I have a optimal stopping problem that is solved by recursion. I was stumped by this question in an interview once. I am hoping someone can walk me through the reasoning so I can reproduce it on similar problems.
Imagine you are playing a card game you start with a well shuffled deck of $52$ cards, stacked face down. You have a sequence of turns, $52$ possible turns in total, each turn you either pull the top card and turn it over, or you quit. If you pull a red card you win $1$, and if you pull a blue card you lose $1$. If you played all $52$ turns without stopping you are guaranteed to break even. What is the optimal stopping strategy?
The solution at the time involved recursion, or a recursion equation. The base cases are that if you know the deck has only red cards remaining (i.e. all $26$ black cards have been pulled) you keep playing until finished. If you know the deck has only black cards remaining, you definitely stop. Working back from this, you get the policy.
But I don't recall the notation for writing this policy/decision rule. I suspect it looks something like a difference or recursion equation, but I'm not sure.