5 递归

5.1 递归

5.1.1 概念

递归是一种直接或者间接调用自身函数。

5.1.2 原理

把问题分解成规模缩小的同类问题的子问题
类似“套娃”

5.1.3 递归的套路

• 确定递归公式
• 确定边界条件

实例：求1~n的和

int sum(int n){
    if(n == 1) return 1;
    return n+sum(n-1);
}

实例：求斐波那契数f(n) = f(n-1) + f(n-2)

// 1 1 2 3 5 8 13...
// 递归
int Fib(int n){
    if(n == 0) return 0;
    if(n == 1 || n == 2) return 1;
    return Fib(n-1) + Fib(n-2);
}

5.2 迭代

5.2.1 概念

迭代（辗转法）是一种不断用变量的旧值递推新值的过程。

5.2.2 本质

迭代很多时候就是使用循环实现

5.2.3 迭代套路

• 确定迭代变量：确定一个直接或间接地不断由旧值推断新值的变量，如sum。

• 建立迭代关系式：从变量的旧值推断到新值的公式，如f(n) = f(n-1) + f(n-2)

• 对迭代过程进行控制：迭代不可能无限循环下去，需要对何时退出迭代进行控制，如i=>n退出循环。

实例：求1~n的和

int sum1(int n){
    int sum = 0;
    for(int i = 1;i <= n;++i){
        sum += i;
    }
    return sum;
}

实例：求斐波那契数f(n) = f(n-1) + f(n-2)

// 1 1 2 3 5 8 13...
// 迭代
int Fib2(int n){
    if(n == 0) return 0;
    if(n == 1 || n == 2) return 1;

    int a = 1;
    int b = 1;
    for(int i = 2;i < n;++i){
        int m = a+b;
        b = a;
        a = m;
    }
    return a;
}

5.3 迭代与递归的比较

• 递归可能比较耗内存
• 递归可能比较效率低

实例：打印1~n

#include <stdio.h>
#include <stdlib.h>
void PrintN(int count,int n){
    if(count > n) return;
    if(count <= n){
        printf("%d ",count);
        PrintN(count+1,n);
    }
}
int main(){
    int n;
    scanf("%d",&n);
    //迭代
    for(int i = 1;i <= n;++i){
        printf("%d ",i);
    }
    printf("\n");
    //递归
    PrintN(1,n);
    printf("\n");
}

• 几种排序算法的递归和迭代比较

1、选择排序

int FindMax(int* arr,int n){
    int index = 0;
    for(int i = 0;i < n;++i){
        if(arr[i] > arr[index]){
            index = i;
        }
    }
    return index;
}
void swap(int* a,int* b){
    int c = *a;
    *a = *b;
    *b = c;
}
/* 
void SelectionSort(int* arr,int n){
    for(int i = 0;i < n;++i){
        int index = FindMax(arr,n-i);
        swap(arr+index,arr+n-1-i);
    }
}
*/ 
void SelectionSort(int* arr,int n){
    if(0 == n) return;
    int index = FindMax(arr,n);
    swap(arr+index,arr+n-1);
    SelectionSort(arr,n-1);
}

2、冒泡排序

void Bubble(int* arr,int n){
    for(int i = 0;i < n-1;++i){
        if(arr[i] > arr[i+1]){
            swap(arr+i,arr+i+1);
        }
    }
}
/*
void BubbleSort(int* arr,int n){
    for(int i = n;i > 0;--i){
        Bubble(arr,i);
    }
}
*/
void BubbleSort(int* arr,int n){
    if(0 == n) return;
    Bubble(arr,n);
    BubbleSort(arr,n-1);
}