递归——让思维更自然

环着色

n个方格摆成一个环，使用红、粉、绿三种颜色着色，相邻方格颜色不同，求可能的着色数。

使用三种颜色着色n个方格的环等价于先使用三种颜色着色n-1个方格的环，着色最后一个方格时，有两种可能情形，左边和右边方格颜色不同，此时可以着上一种颜色，左边和右边方格颜色相同，可以着上两种颜色。

color(n)=color(n-1)+color(n-2)*2

字符串

一个长为n的字符串，可以含有字符a、b、c、d，a、c只可以出现偶数次，b、d可以随意出现。求可能的字符串数。

一个长度为n的字符串可以分成：a奇c奇、a偶c奇、a奇c偶、a偶c偶。

aoco(1)=0

aeco(1)=1

aoce(1)=1

aece(1)=2

aoco(n)=2*aoco(n-1)+aeco(n-1)+aoce(n-1)

aeco(n)=2*aeco(n-1)+aoco(n-1)+aece(n-1)

aoce(n)=2*aoce(n-1)+aece(n-1)+aoco(n-1)

aece(n)=2*aece(n-1)+aoce(n-1)+aeco(n-1)

递归式的一些性质

aoco(n)+aeco(n)+aoce(n)+aece(n)=2^(2n)

aoco(n)+aece(n)=2^(2n-1)

aoco(n)=aoco(n-1)+2^(2n-2)-aece(n-1)=2*aoco(n-1)+2^(2n-3)

aoco(n)/2^(n)=aoco(n-1)/2^(n-1)+2^(n-3)

通项公式

aoco=2^(2n-2)-2^(n-1)

aeco=2^(2n-2)

aoce=2^(2n-2)

aece=2^(2n-2)+2^(n-1)