递归算法-汉诺塔

递归算法（英语：recursion algorithm）在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法。递归的突然好空是函数可以通过调用自身来进行递归。其中直接调用自己称为直接递归，而将调用b，b又调用a的递归叫做间接递归。
递归算法的效率比较低，时间和空间开销都很大，但逻辑关系清晰，程序简洁，增加了可读性。

例1 斐波那契数列:

//Fibonacci Series using Recursion
#include<iostream>
using namespace std;
 
int fib(int n){
    if (n <= 1)
        return n;
    return fib(n-1) + fib(n-2);
}
 
int main (){
    int n ;
    cin>>n;
    cout << fib(n);
    return 0;
}

例2 二分查找：设有n个数已经从大到小的顺序排列好，现在输入某数x，判断它是否在这个数列里，如果存在，输出位置。

// C++ program to implement recursive Binary Search
#include <iostream>
using namespace std;

// A recursive binary search function. It returns
// location of x in given array arr[l..r] is present,
// otherwise -1
int binarySearch(int arr[], int l, int r, int x)
{
	if (r >= l) {
		int mid = l + (r - l) / 2;

		// If the element is present at the middle
		// itself
		if (arr[mid] == x)
			return mid;

		// If element is smaller than mid, then
		// it can only be present in left subarray
		if (arr[mid] > x)
			return binarySearch(arr, l, mid - 1, x);

		// Else the element can only be present
		// in right subarray
		return binarySearch(arr, mid + 1, r, x);
	}

	// We reach here when element is not
	// present in array
	return -1;
}

int main(void)
{
	int n,x,arr[100];
    cin>>n;
    for (int i = 0; i <n; i++)
    {
        cin>>arr[i];
    }
    cin>>x;
	int result = binarySearch(arr, 0, n - 1, x);
	(result == -1)
		? cout << "Element is not present in array"
		: cout << "Element is present at index " << result;
	return 0;
}

例三：汉诺塔游戏

#include <iostream>
using namespace std;
void Move(int n, char A, char B, char C)
{
    if (n == 1)
    {
        //圆盘只有一个时，只需将其从A塔移到C塔
        cout << "move " << n << " from " << A << " to " << C << endl;
        }
        else
        {
            Move(n - 1, A, C, B);//递归，把A塔上编号1~n-1的圆盘移到B上，以C为辅助塔
            cout << "move " << n << " from " << A << " to " << C << endl;//把A塔上编号为n的圆盘移到C上
            Move(n - 1, B, A, C);//递归，把B塔上编号1~n-1的圆盘移到C上，以A为辅助塔
            }
}
int main() {
    int n;
    cin>>n;
    Move(n, 'A', 'B', 'C');
    return 0;
    
}

洛谷：P1242

Previous Topic

Back to Lesson

Next Topic

数据结构与算法

递归算法-汉诺塔