换硬币 （C++代码）递归

解题思路:

注意事项:

参考代码:

 /*

这一题我们可以这样子来想递归的，题意是输入N,样例是4，只有1元和2元来分4元

所以，就是把4拆分成多个1和2的组合

所以就是4要么-1，4要么-2

样例如下所示：

4=1+1+1+1
4=2+1+1
4=1+2+1
4=1+1+2
4=2+2

样例是加法，其实也是减法，4减1，或者4减2

递归的结束条件就是当x==0的时候

所以，我用递归的思路是先减1，然后就是减2

然后在减1或者减2之后，进入新的递归函数里，判断减去之后的x是否等于0，等于0那就

说明这是一个合适的拆分种类，于是sum++，结束当前递归，返回之前的上一步

就拿4来说

a层：digui(4);x= 4，进入这个函数，两个if不合适条件，来到digui(x-1),也就是递归(3)，进入digui(3);

b层：digui(3);x = 3,进入这个函数，两个if不合适条件，来到digui(x-1),也就是递归(2)，进入digui(2);

c层： digui(2)  ; x = 2,进入这个函数，两个if不合适条件，来到digui(x-1),也就是递归(1)，进入digui(1);

d层：digui(1);x = 1,进入这个函数，两个if不合适条件，来到digui(x-1),也就是递归(0)，进入digui(0);

e层：digui(0);x = 0.进入这个函数，满足了第一个if的条件x==0，然后sum++,结束e层，返回上一层d层。        (从a层看到e层你就可以发现是 4=(a层)1+(b层)1+(c层)1+(d层)1也就是样例的第一个4=1+1+1+1。)

d层：digui(1);x = 1,进入这个函数，digui(x-1)已经运行过了，接下来是下一句代码

digui(x-2);也就是digui(-1),进入e层。

e层：digui(-1);x=-1,进入这个函数，第一个if的x==0不符合，来到下一个if,x<0,x=-1,-1<0,拆分钱不会拆到自己还要给钱的吧？也就是不可能为负数的，然后return,结束e层，返回d层；

d层：digui(1);x = 1,进入这个函数，digui(x-1)和digui(x-2)都已经运行过了，接下来是下一句代码return. 说明d层已经减1和减2都尝试过了，然后结束d层，返回上一层c层，进入c层

............................然后急救按照这样子的思路一直往下走，返回上一层，进入下一层，（太多了，懒得写了......写不动写不动.......）

所以这个递归先判断是否等于0或者小于0，满足0就sum++，结束当前层，返回上一层

然后每一次是先-1，然后在-2，-1进入下一层

*/

#include<iostream>

using namespace std;

int sum = 0;       //记录多少种的数目

void digui(int x){

    if (x == 0){sum++;return;}

    if (x < 0)return;

    digui(x - 1);

    digui(x - 2);

    return;

}

int main(){

    int x;

    cin >> x;

    digui(x);

    cout << sum;

    return 0;

}