简单来说,递归就是程序不断调用自身的一种方法。构成递归当然是有条件的,条件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.递归并非绝佳的解决方式。不要盲目的选择递归。