Recursion is a general technique with wide application. When it is used to solve a counting problem, the basic principle is the same:
- Let $P(n)$ be the count when there are $n$ objects
- Find the relation between $P(n)$ and $P(n-1)$
- Manually solve the case $P(1)$
- Solve $P(n)$ which is the answer
If you are familiar with the mathematical induction, the steps presented here are almost identical to those you will use in applying induction.
Derive the permutation formula $P_n^n=n\times (n-1)\times\cdots\times 2\times 1$ using the recursion method.(4772)
(Hanoi Tower) There are $3$ identical rods labeled as $A$, $B$, $C$; and $n$ disks of different sizes which can be slide onto any of these three rods. Initially, the $n$ disks are stacked in ascending order of their sizes on $A$. What is the minimal number of moves in order to transfer all the disks to $B$ providing that each move can only transfer one disk to another rod's topmost position and at no time, a bigger disk can be placed on top of a smaller one.(4478)