算法解读 ---- 递归（一）

算法解读 ---- 递归（一）

算法的最重要的是算法设计的模型，以及该模型背后的设计思想。

定义：
递归从编程的角度上理解：递归就是一个过程或者函数在其定义中直接或间接调用自身的一种方法。

递归是一种用来描述问题和解决问题的基本方法。

特点：
通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。

一般说来，递归需要有边界条件、递归前进段和递归返回段、当边界条件不满足时，递归前进；当边界条件满足时，递归返回。

递归算法：
第一步：将原问题分解多个具有类似于原问题特性的子问题。（递归关系）
第二步：确定一个或者多个无须分解、可直接求解的最小子问题（递归的终止条件）

举例：

输入两个整数x,n,计算x 的n次幂，结果对10000007取模。

问题描述：

上述题意：可归结为：
1、递归关系：x^n = x*x^(n-1)
2、边界条件：当n=0时候，x=1

参考代码：

#include <QCoreApplication>

#include<iostream>

#define MOD 10000007

long long power(int x,int n)
{
    long long ans;
    if(n==0) ans = 1;
    else
    {
        ans=x*power(x,n-1)%MOD;
    }

    return ans%MOD;
}

using namespace std;

int main(int argc, char *argv[])
{
    QCoreApplication a(argc, argv);

    int x;
    int n;
    cout<<"please Enter x:" <<endl;
    cin>>x;
    cout<<"please Enter n:"<<endl;
    cin>>n;
    
    cout<<"the answer is :"<<power(x,n);

    return a.exec();
}