C++递归之汉诺塔

　　简单来说，递归就是程序不断调用自身的一种方法。构成递归当然是有条件的，条件1：子问题需要与原问题是同一件事，而且要更加简单了。条件2：调用不能无限制，必须有一个终止条件。

　　在数学和计算机科学中，递归指的是由一种简单的基本情况定义的一类对象或者方法，并规定其他所有情况都能被还原为基本情况。

　　典型的递归问题有《斐波那契数列》《汉诺塔》《上楼梯》等，这次随笔记录汉诺塔问题。

　　既然是原问题分解成子问题，我们需要从最小的问题开始看。

　　汉诺塔的由来就不再赘述，假设有A,B,C三根柱子。那么如果有1块饼，简单！一次就到位了。

　　2块饼的时候，从下往上定为cake[0]、cake[1]。那么cake[1]先到B柱，cake[0]到C柱，cake[1]再到C柱，完成。

　　3块饼的时候，我们不难发现所有的操作其实都归结到了两块饼的操作上（如果有图示会更加明确）由此我们可以推断出f(n) = 2 * f(n) + 1这样一个递归公式来。还要补充当n = 1时，f(n) = 1。

//
//  main.cpp
//  HanoTower
//
//  Created by MadMarical on 15/11/23.
//  Copyright (c) 2015年 com. All rights reserved.
//

#include <iostream>

using namespace std;

int count(int n)
{
    int cnt;
    if (n == 1)
    {
        cnt = 1;
    }
    else
    {
        cnt = 2 * count(n - 1) + 1;
    }

    return cnt;
}

int main(int argc, const char * argv[])
{
    int n;
    cin>>n;
    int ans = count(n);
    cout<<ans<<endl;
    return 0;
}

反思：

1.递归思想在程序运用中特别重要，明确开始和结尾就是递归的核心部分。

2.递归并非绝佳的解决方式。不要盲目的选择递归。