递归的基础运用

递归:函数自己调用自身的行为叫做递归。

递归的基本形式:其本身为一种结构

#include <iostream>
using namespace std;
void f()
{
    f();//函数自己调用自身
}
int main()
{
    f();
}

如果我们运行上面的代码,便会出现一个名为Stack overflow的异常(栈溢出

因为上面我们讲到,递归是一种栈结构,而栈是一种先进后出的结构,而上面的代码由于没有定义递归的出口,所以会导致递归无法终止,所以为了避免栈溢出,我们应该定义一个递归的出口:

#include <iostream>
using namespace std;
void f(int i)
{
    if(i>0)
        f(i-1);//函数自己调用自身
    else return;//定义递归出口:当i<=0时,递归结束
}
int main()
{
    f(10);
}

那么什么叫做先进后出呢,举个例子说明:

F(10)中调用其本身,i-1,变为了F(9),
F(9)中又调用了其本身,i-1,变为了F(8)
...
F(1)中又调用了其本身,i-1,i变为了0
i=0了,递归开始结束,层层返回。
F(1)
F(2)
...
F(10)
递归结束


通过上面的分析,我们不难发现,最先进栈的F(10)是最后返回的,而最后进栈的F(1),却是最先返回的。这种关系叫做先进后出(LIFO).

1.解递归问题的两种思维之切蛋糕思维

例子1:求N的阶乘:

/*递归问题求解的基本思路:
*找重复(找到子问题)
*找变化
*找边界:出口
*/
#include <iostream>
using namespace std;
int f(int n)
{
    if (n == 1)  return 1;//定义递归出口
    else
    return n * f(n - 1);//将原问题分解为子问题

}
int main()
{
    int n;
    cin >> n;
    cout<<f(n);
}

运行结果

例子2:打印b-g:

#include <iostream>
using namespace std;
void f(char a,const char& b)
{
    cout << a << " ";
    if (a== b)  return ;//定义递归出口
    else
    return f(++a,b);//找到重复(子问题)

}
int main()
{
    f('b','g');
}

运行结果:

例子3:对数组的所有元素求和

#include <iostream>
#include <vector>
using namespace std; 
int f(const vector<int> &arr,int p)//如果发现递归写不出来,那么加参数试试
{
    if (p== arr.size()-1) return arr[p];//定义递归出口,当p下标达到数组末尾时。返回末尾的数,递归开始层层返回
    return arr[p] + f(arr, p+1);//子问题:求数组中的一个数,和剩下的数的和
}

int main()
{
    int in[5] = { 1,2,3,4,5};
    vector<int> arr(in, in + 5);//初始化数组
    cout<<f(arr,0);

}

运行结果

例子4:翻转字符串

#include <iostream>
#include <string>
using namespace std;
char f(string  str,int p)
{
    if (p == 0) return str[p];//定义递归出口
    cout << str[p];//打印翻转的字符
    return f(str, p-1);//子问题:打印最末尾的字符,然后逆序打印
}

int main()
{
    string str;
    getline(cin, str);//为了输入空格
    cout<<f(str,str.size()-1);
    return 0;
}

总结:在重复中找变化,在变化中找重复

2.多分支递归:分解为多个子问题

单分支递归:

多分支递归:先横后纵

例:求第N项斐波那契数列

斐波那契数列(意大利语:Successione di Fibonacci),又译为菲波拿契数列、菲波那西数列、斐波那契数列、黄金分割数列。
在数学上,费波那契数列是以递归的方法来定义:

用文字来说,就是费波那契数列由0和1开始,之后的费波那契系数就是由之前的两数相加而得出。首几个费波那契系数是:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233……(OEIS中的数列A000045)
特别指出:0不是第一项,而是第零项。
维基百科-斐波那契数列

求斐波拉契数列的第N项的递归实现是一个典型的双分支递归。
代码实现

#include <iostream>
#include <string>
using namespace std;
int f(int n)
{
    if (n == 1||n==2) return 1;//定义递归出口
    return f(n - 1) + f(n - 2);//双分支递归,上面多分枝递归的结构就是斐波拉契数列的
}

int main()
{
    int n;
    cin >> n;
    cout << f(n);
    return 0;
}

运行结果

2.解递归问题的两种思维之递推公式,等价转换

例1.辗转相除法的递归形式:

在数学中,辗转相除法,又称欧几里得算法(英语:Euclidean algorithm),是求最大公约数的算法。辗转相除法首次出现于欧几里得的《几何原本》(第VII卷,命题i和ii)中,而在中国则可以追溯至东汉出现的《九章算术》。
两个整数的最大公约数是能够同时整除它们的最大的正整数。辗转相除法基于如下原理:两个整数的最大公约数等于其中较小的数和两数的差的最大公约数。例如,252和105的最大公约数是21,因为 252 − 105 = 21 × (12 − 5) = 147 ,所以147和105的最大公约数也是21。在这个过程中,较大的数缩小了,所以继续进行同样的计算可以不断缩小这两个数直至其中一个变成零。这时,所剩下的还没有变成零的数就是两数的最大公约数。由辗转相除法也可以推出,两数的最大公约数可以用两数的整数倍相加来表示,如 21 = 5 × 105 + (−2) × 252 。这个重要的结论叫做裴蜀定理。
维基百科-辗转相除法


图解:
辗转相除法图解


定理:gcd(a,b) = gcd(b,a mod b)
证明:a可以表示成a = kb + r,则r = a mod b
假设d是a,b的一个公约数,则有
d|a, d|b,而r = a - kb,因此d|r
因此d是(b,a mod b)的公约数
假设d 是(b,a mod b)的公约数,则
d | b , d |r ,但是a = kb +r
因此d也是(a,b)的公约数
因此(a,b)和(b,a mod b)的公约数是一样的,其最大公约数也必然相等,得证
最大公约数(Gcd)两种算法(Euclid && Stein)

代码实现:

#include <iostream>
using namespace std;
int f(int m, int n)
{
    if (n == 0)return m;
    return f(n, m % n);
}

int main()
{
    int m, n;
    cin >> m >> n;
    cout << f(m, n);
    return 0;
}

插入排序的递归形式

#include <iostream>
#include <string>
#include <vector>
using namespace std;
void f(vector<int>& nums, int p)
{
    if (p == 0) return;
     f(nums, p - 1);
    int index = p - 1;
    int x = nums[p];
    while (x>nums[index])    
    {
        nums[index+ 1] = nums[index];
        index--;
    }
    nums[index+1]=x;
    
}
int main()
{
    int in[] = { 45,12,13,445,233 };
    vector<int>nums(in, in + 5);
    nums.push_back(0);
    f(nums,5);
    for (int i = 0; i < nums.size(); i++)
    {
        cout << nums[i] << " ";
    }
    return 0;
}

汉诺塔问题

汉诺塔(港台:河内塔)是根据一个传说形成的数学问题:
有三根杆子A,B,C。A杆上有 N 个 (N>1) 穿孔圆盘,盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至 C 杆:
每次只能移动一个圆盘;
大盘不能叠在小盘上面。
提示:可将圆盘临时置于 B 杆,也可将从 A 杆移出的圆盘重新移回 A 杆,但都必须遵循上述两条规则。
问:如何移?最少要移动多少次?

对于汉罗塔问题的递归求解的理解,参考invalid s的回答
原文如下:

递归只能以递归的思路理解,把它展开纯属自讨苦吃。递归思路,说白了是如下三步:
1、对于问题N,如果N-1已经解决了,那么N是否很容易解决。
甲:想上天?你先给我找个天一样高的梯子!
乙:想要天一样高的梯子?你先给我弄棵天一样高的树!
甲:想要天一样高的树?你先给我弄把能顶到天的锯子!
举例来说,如果要把一个N层汉诺塔从A搬到C,那么:如果前N-1层可以找别人搞定,咱只管搬第N层,会不会变得非常容易?你看,这一下就简单了:这时当它只有两层就好了,
先把前N-1层看作一个整体,把它搬到B;
然后把最下面的第N层搬到C;
然后再把前N-1层从B搬到C。
类似的,假如接到“搬前N-1层”这个任务的是我们,怎么搬呢?简单,像前东家一样,把前N-2层外包出去,我们只搬第N-1层——其实和前面讨论过的“外包N-1层,只搬第N层”完全一样。
依此类推,一层层“外包”下去——我不管你们有多伤脑筋,反正只要你们把我外包给你的活干了,我就能干了我的活!
注意,这里千万别管“接到外包工作的家伙有多伤脑筋”——丢给他就让他头疼去,我们就别再捡回来痛苦自己了。
这一步就是“递推”。
注意这里的搬法:搬第N层,就需要把前N-1层搬两次,另外再把第N层搬一次;
搬第N-1层,又需要把前N-2层搬两次,然后再把N-1层搬一次。
依此类推。很容易知道,一共需要搬2^N-1次。2、一步步递推下去,终究会有个“包工头”,接到“搬第一层”的任务。第一层怎么搬?太简单了,让搬哪搬哪。换句话说,到此,“递推”就到了极限,简单粗暴直接做就可以了。3、既然第一层搬了,那么第二层当然就可以搬了;第二层搬了,第三层又可以搬了……依次类推,直到第N层。于是问题搞定。这一步就是“回归”。如上三步加起来,就是“递归”。
推而广之,任何问题,不管规模为N时有多复杂,只要把N-1那块“外包”给别人做之后,我们在这个基础上可以轻易完成N,那么它很可能就适合用“递归”解决。
那么,怎么最终确定它能不能用“递归”做呢?看当N取1或2之类最简情况时,问题是否可以解决——然后写程序解决它。
容易看出,“递归”其实和“数学归纳法”的思路非常像:证明N=1时成立;证明若N=n-1成立,则N=n时也成立;如上两步得证,则命题在n>1时一定成立(n为自然数)。你看,我们没必要从1开始逐一验证每个自然数,只要证明了“基础条件”、再证明了“递推条件”,大自然的规律会帮我们搞定一切。
换句话说,只要我们:
1、写程序告诉电脑“如何分解一个问题”
2、写程序告诉电脑“当该问题分解到最简时如何处理”
那么,“具体如何递推、如何回归”这个简单问题就不要再操心了,电脑自己能搞定。——写出问题分解方法、写出分解到最简后如何解决,这是我们的任务;把问题搞定,是电脑的任务。这就是递归的魅力。正是由于这种“我提供思路你搞定细节”的特点,“一切皆递归”的函数系语言才被称为“声明式编程”(而不是必须一步一步指导电脑如何做的“命令式编程”)。这么简单轻松的事,非要自己吭哧吭哧一步步做出来——O(2^N)规模啊——难怪你们要陷入困境。
如何理解汉诺塔的递归? - invalid s的回答 - 知乎

代码实现:

#include <iostream>
#include <string>
#include <vector>
using namespace std;
void f(int n,string  from,string to ,string fz)
{
    if (n == 0)
    {
        cout << "把" << n << "从" << from << "移动到" << to<<endl;
    }
    else
    {
        f(n - 1, from, fz, to);
        cout << "把" << n << "从" << from << "移动到" << to<<endl;
        f(n - 1, fz, to, from);
    }
}
int main()
{
    f(3, "a", "c", "b");
    return 0;
}

运行结果:

二分查找的递归解法

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int efcz(const vector<int> &nums,const int& find,int start,int end)
/*nums:要查找的数组
*要查找的数
*start:起始下标
*end:结束下标
*/
{
    if (start > end)return -1;//定义递归出口
    int mid = start + ((end - start) >> 1);//防止溢出,等于int mid = start + ((end - start) / 2)。其和/2的区别如上图
    if (find <nums[mid])//多分支递归,但最终要剪枝
    {
        return efcz(nums, find, start, mid-1);
    }
    else if (find > nums[mid])
    {
        return efcz(nums, find, mid + 1, end);
    }
    else
    {
        return mid;
    }
}
int main()
{
    int in[] = { 1,2,54,45,65,46,546,2213,12,312,312,31 };
    vector<int>nums(in, in + 12);//初始化数组
    sort(nums.begin(), nums.end());//进行二分排序的数组必须是有序的
    int n;
    cin >> n;//输入要查找的数
    int p = efcz(nums, n, 0, 11);//调用函数
    if (p != -1)cout << nums[p];//通过返回的下标输出对应值
    else cout << "找不到";
    return 0;
}

运行结果:

二分查找的递归形式和多分支递归的区别:


知识共享许可协议
本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。

Last modification:May 29th, 2019 at 04:01 pm
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment