印度阿三17 / 开发 / 递归

分享

   

递归

2020-02-21  印度阿三17

递归算法简单的讲就是:一个函数调用其本身。
他是通过重复将问题分解为同类的子问题而解决问题的方法。
递归与普通的调用没有本质的差别,都是一个函数调用一个函数,只不过这个函数是他本身。函数调用都是通过栈来实现的。每一个应用程序运行时都有一定的内存属于他。栈是专门用来函数调用的,就是你这个函数调用了,栈就会向上伸展一层。伸展这一层存放的就是这次函数调用的形参,局部变量以及返回地址。当函数调用结束时,栈顶上还会存放这次函数调用的返回值。
那么程序设计中,递归到底有什么用呢。那么用法就太多了,我们主要分为三类:
①.替代多重循环。
②.问题本来就是以递归形式定义的问题。
③.能重复将问题分解为同类的子问题而解决的问题。
………………


递归的两个必要条件
1、存在限制条件,当满足这个条件时,递归便不再继续。这个条件可以是多个。
2、每次递归调用之后越来越接近这个限制条件。


1.汉诺塔问题
问题描述:古代有个樊塔,塔内有三座A、B、C,A座上有64个盘子,盘子大小不等,大的在下,小的在上。有一个和尚想把这64个盘子从A座移动到C座,单每次只能允许移动一个盘子,并且在移动过程中,3个座上的盘子始终保持大盘在下,小盘在上。在移动过程中可以利用B座,要求输出移动的步骤。
基本思路就是:先将N-1个盘子放到B座,然后把剩下的最大的盘子移动到C座,然后把B座上的N-1个盘子移动到C座。

#include <iostream>
using namespace std;
void Hanoi(int n,char src,char mid,char dest)
{
    if(n == 1){  //只有一个盘子 ,只需移动一次 
        cout << src << "->" << dest << endl;
        return;
    } 
    Hanoi(n-1,src,dest,mid);  //先将n-1个盘子从scr移动到mid
    cout << src << "->" << dest << endl;  //再将一个盘子从src移动到dest 
    Hanoi(n-1,mid,src,dest);  //最后把n-1的盘子从mid移动到dest
    return; 
 } 
 
int main()
{
    int n;
    cin >> n;  //输入盘子数目 
    Hanoi(n,'A','B','C'); 
    return 0;
}

运行结果:

4
A->B
A->C
B->C
A->B
C->A
C->B
A->B
A->C
B->C
B->A
C->A
B->C
A->B
A->C
B->C

因为如果有64个盘子,输出结果庞大,所以这里带入的是四个盘子。

2.求n!的递归函数

#include <stdio.h>

int Factorial(int n)
{
    if(n == 0)
        return 1;
    else
        return n * Factorial(n - 1);
 } 
 
int main()
{
    int a = Factorial(5);
    printf("%d",a);
    return 0;
}

运行结果:

120
来源:

    本站是提供个人知识管理的网络存储空间,所有内容均由用户发布,不代表本站观点。请注意甄别内容中的联系方式、诱导购买等信息,谨防诈骗。如发现有害或侵权内容,请点击一键举报。

    0条评论

    发表

    请遵守用户 评论公约

    类似文章 更多
    喜欢该文的人也喜欢 更多

    ×
    ×

    ¥.00

    微信或支付宝扫码支付:

    开通即同意《个图VIP服务协议》

    全部>>