递归入门

1.递归求前n项和

所有循环都可以转化为递归,而递归大多数可以转换为循环

#include <iostream>
using namespace std;

int sum(int a[],int n)
{
    if(n==0)
        return a[0];
    else
        return sum(a,n-1) + a[n];
}
int main()
{
    int a[] = {1,2,3,4,5};
    cout<<sum(a,4);
    return 0;
}

2.递归求最大值

数组第一个下标与最后一个下标相同时,也就是只有一个元素时,是递归的出口

    if(left == right)
        return a[left];

否则就将第一个元素与后面所有元素的最大值相比较

    else{
        int m = a[left];
        int n = findMax(a,left+1,right);
        if(m>n)
            return m;
        else
            return n;

    }

完整代码

#include <iostream>
using namespace std;

int findMax(int a[],int left,int right)
{
    if(left == right)
        return a[left];
    else{
        int m = a[left];
        int n = findMax(a,left+1,right);
        if(m>n)
            return m;
        else
            return n;

    }
}
int main()
{
    int a[5] = {5,22,8,3,1};
    cout<<findMax(a,0,4);
    return 0;
}

3.递归求和

思路和求最大值相似

int sum(int arr[],int left,int right)
{
    if(left == right)
        return arr[left];
    else
    {
        return arr[left] + sum(arr,left+1,right);
    }
}

4.递归冒泡

int bubble(int arr[],int left,int right)
{
    if(left == right)
        return 0;
    else
    {
        for(int i=left;i<=right-1;i++)
        {
            if(arr[i]>arr[i+1])
            {
            int tmp  = arr[i];
            arr[i] = arr[i+1];
            arr[i+1] = tmp;
            }
        }
        bubble(arr,left,right-1);
    }
}

5.递归求最大公约数

int gcd(int a,int b)
{
    int r = a % b;
    if(r == 0)
        return b;
    else{
        return gcd(b,r);
    }
}