1. 　　递归就是在过程或函数里调用自身。
2. 　　在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。
3. 　　递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序。
4. 　　在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。所以一般不提倡用递归算法设计程序。

下面来详细分析递归的工作原理。

先看看C语言中函数的执行方式，需要了解一些关于C程序在内存中的组织方式：

堆的增长方向为从低地址到高地址向上增长，而栈的增长方向刚好相反（实际情况与CPU的体系结构有关）。

当C程序中调用了一个函数时，栈中会分配一块空间来保存与这个调用相关的信息，每一个调用都被当作是活跃的。

栈上的那块存储空间称为活跃记录或者栈帧。

栈帧由5个区域组成：输入参数、返回值空间、计算表达式时用到的临时存储空间、函数调用时保存的状态信息以及输出参数，参见下图：

#define _CRT_SECURE_NO_WARNINGS  //避免scanf报错
#include <stdio.h>

int main(void)
{
    int sumInt = fact(3);
    printf("3的阶乘为：%d\n", sumInt);
    system("PAUSE");//结束不退出
}

//递归求阶乘
int fact(int n) {
    if (n < 0)
        return 0;
    else if (n == 0 || n == 1)
        return 1;
    else
        return n * fact(n - 1);
}

#define _CRT_SECURE_NO_WARNINGS  //避免scanf报错
#include <stdio.h>

void main(void)
{
    printf("%d \n", fibonacci(10));
    system("PAUSE");//结束不退出
}

//斐波那契数列，第一二项为1；后面的每一项为前两项之和
int fibonacci(int a){
    if (a == 1 || a == 2)
    {
        return 1;
    }
    else{
        return fibonacci(a - 1) + fibonacci(a - 2);
    }
}

#define _CRT_SECURE_NO_WARNINGS  //避免scanf报错
#include <stdio.h>

void main(void)
{
    char str[100];
    int i;
    printf("enter a integer:\n");
    scanf("%d", &i);
    toString(i, str);
    puts(str);
    system("PAUSE");//结束不退出
}

//递归将整形数字转换为字符串 
int toString(int i, char str[]){
    int j = 0;
    char c = i % 10 + '0';
    if (i /= 10)
    {
        j = toString(i, str) + 1;
    }
    str[j] = c;
    str[j + 1] = '\0';
    return j;
}

#define _CRT_SECURE_NO_WARNINGS  //避免scanf报错
#include <stdio.h>

//递归汉诺塔
void hanoi(int i, char x, char y, char z){
    if (i == 1){
        printf("%c -> %c\n", x, z);
    }
    else{
        hanoi(i - 1, x, z, y);
        printf("%c -> %c\n", x, z);
        hanoi(i - 1, y, x, z);
    }
}

void main(void)
{
    hanoi(10, 'A', 'B', 'C');
    system("PAUSE");//结束不退出
}

#define _CRT_SECURE_NO_WARNINGS  //避免scanf报错
#include <stdio.h>

//猴子吃桃，每天吃一半再多吃一个，第十天想吃时候只剩一个 
int chitao(int i){
    if (i == 10){
        return 1;
    }
    else{
        return (chitao(i + 1) + 1) * 2;
    }
}

void main(void)
{
    printf("%d", chitao(5));
    system("PAUSE");//结束不退出
}

#define _CRT_SECURE_NO_WARNINGS  //避免scanf报错
#include <stdio.h>

/*======================N皇后问题========================*/
#define N 100

int q[N];//列坐标

//输出结果
void dispasolution(int n)
{
    static int count = 0;
    printf("  第%d个解:", ++count);
    for (int i = 1; i <= n; i++)
    {
        printf("(%d,%d) ", i, q[i]);
    }
    printf("\n");
}

//判断位置(i,j)能否放皇后
int place(int i, int j)
{
    //第一个皇后总是可以放
    if (i == 1)
        return 1;
    //其他皇后不能同行，不能同列，不能同对角线
    int k = 1;

    //k~i-1是已经放置了皇后的行
    while (k < i)
    {
        if ((q[k] == j) || (abs(q[k] - j) == abs(i - k)))
            return 0;
        k++;
    }
    return 1;
}

//放置皇后
void queen(int i, int n)
{
    if (i > n)dispasolution(n);
    else
    {
        for (int j = 1; j <= n; j++)
        {
            if (place(i, j)==1)
            {
                q[i] = j;
                queen(i + 1, n);
            }
        }
    }

}

int main()
{
    queen(1, 4);
    system("PAUSE");//结束不退出
}

#define _CRT_SECURE_NO_WARNINGS  //避免scanf报错
#include <stdio.h>

//冒泡排序
//交换 a 和 b 的位置的函数
void swap(int *a, int *b);
void main()
{
    int array[8] = { 49, 38, 65, 97, 76, 13, 27, 49 };
    int i, j;
    int key;
    //有多少记录，就需要多少次冒泡，当比较过程，所有记录都按照升序排列时，排序结束
    for (i = 0; i < 8; i++){
        key = 0;//每次开始冒泡前，初始化 key 值为 0
        //每次起泡从下标为 0 开始，到 8-i 结束
        for (j = 0; j + 1<8 - i; j++){
            if (array[j] > array[j + 1]){
                key = 1;
                swap(&array[j], &array[j + 1]);
            }
        }
        //如果 key 值为 0，表明表中记录排序完成
        if (key == 0) {
            break;
        }
    }
    for (i = 0; i < 8; i++){
        printf("%d ", array[i]);
    }
    system("PAUSE");//结束不退出
}
void swap(int *a, int *b){
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

#define _CRT_SECURE_NO_WARNINGS  //避免scanf报错
#include <stdio.h>
#include <stdlib.h>
#define MAX 9
//单个记录的结构体
typedef struct {
    int key;
}SqNote;
//记录表的结构体
typedef struct {
    SqNote r[MAX];
    int length;
}SqList;
//此方法中，存储记录的数组中，下标为 0 的位置时空着的，不放任何记录，记录从下标为 1 处开始依次存放
int Partition(SqList *L, int low, int high){
    L->r[0] = L->r[low];
    int pivotkey = L->r[low].key;
    //直到两指针相遇，程序结束
    while (low<high) {
        //high指针左移，直至遇到比pivotkey值小的记录，指针停止移动
        while (low<high && L->r[high].key >= pivotkey) {
            high--;
        }
        //直接将high指向的小于支点的记录移动到low指针的位置。
        L->r[low] = L->r[high];
        //low 指针右移，直至遇到比pivotkey值大的记录，指针停止移动
        while (low<high && L->r[low].key <= pivotkey) {
            low++;
        }
        //直接将low指向的大于支点的记录移动到high指针的位置
        L->r[high] = L->r[low];
    }
    //将支点添加到准确的位置
    L->r[low] = L->r[0];
    return low;
}
void QSort(SqList *L, int low, int high){
    if (low<high) {
        //找到支点的位置
        int pivotloc = Partition(L, low, high);
        //对支点左侧的子表进行排序
        QSort(L, low, pivotloc - 1);
        //对支点右侧的子表进行排序
        QSort(L, pivotloc + 1, high);
    }
}
void QuickSort(SqList *L){
    QSort(L, 1, L->length);
}
void main() {
    SqList * L = (SqList*)malloc(sizeof(SqList));
    L->length = 8;
    L->r[1].key = 49;
    L->r[2].key = 38;
    L->r[3].key = 65;
    L->r[4].key = 97;
    L->r[5].key = 76;
    L->r[6].key = 13;
    L->r[7].key = 27;
    L->r[8].key = 49;
    QuickSort(L);
    for (int i = 1; i <= L->length; i++) {
        printf("%d ", L->r[i].key);
    }
    system("PAUSE");//结束不退出
}

#define _CRT_SECURE_NO_WARNINGS  //避免scanf报错
#include <stdio.h>
int binary_search(int key, int a[], int n) //自定义函数binary_search()
{
    int low, high, mid, count = 0, count1 = 0;
    low = 0;
    high = n - 1;
    while (low<high)    //査找范围不为0时执行循环体语句
    {
        count++;    //count记录査找次数
        mid = (low + high) / 2;    //求中间位置
        if (key<a[mid])    //key小于中间值时
            high = mid - 1;    //确定左子表范围
        else if (key>a[mid])    //key 大于中间值时
            low = mid + 1;    //确定右子表范围
        else if (key == a[mid])    //当key等于中间值时，证明查找成功
        {
            printf("查找成功!\n 查找 %d 次!a[%d]=%d", count, mid, key);    //输出査找次数及所査找元素在数组中的位置
            count1++;    //count1记录查找成功次数
            break;
        }
    }
    if (count1 == 0)    //判断是否查找失敗
        printf("查找失敗!");    //査找失敗输出no found
    return 0;
}
int main()
{
    int i, key, a[100], n;
    printf("请输入数组的长度：\n");
    scanf("%d", &n);    //输入数组元素个数
    printf("请输入数组元素：\n");
    for (i = 0; i<n; i++)
        scanf("%d", &a[i]);    //输入有序数列到数组a中
    printf("请输入你想查找的元素：\n");
    scanf("%d", &key);    //输入要^找的关键字
    binary_search(key, a, n);    //调用自定义函数
    printf("\n");
    system("PAUSE");//结束不退出;
}

#define _CRT_SECURE_NO_WARNINGS  //避免scanf报错
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <ctype.h>
#define MAX 400000  /** 定义 最大 数组 大小 **///（感觉没啥用 但是最好尽可能开大点，但是不要太大，不要超出系统可建造范围）
typedef struct Node *Hash; /**新的路程又开始了 这次准备用数组来做哈希 还有双向平方处理冲突**/
struct Node{
    char phone[15];
    int num;
};

int maxInt(int x, int y)
{
    if (x>y) return x;
    else return y;
}

char* minstr(char *x, char *y)
{
    if (strcmp(x, y)>0) return y;
    else return x;
}
int nextprime(const int n)
{
    int p = (n % 2 == 1) ? n + 2 : n + 1; /**先找一个大于N的奇数**/
    int i;
    while (p<MAX)
    {
        for (i = (int)sqrt(p); i >= 2; i--)   /**然后再判断是不是素数**/
        if (p%i == 0) break;
        if (i<2) return p;        /**是 那就返回这个数**/
        else p += 2;/**不是 那就下一个奇数**/
    }
}
int deal(char *s, int p) /**然后把字符串映射成下标 (映射的方式很多很多，随便猜一个靠谱的就行了)**/
{
    int index = (atoi(s + 2)) % p;
    return index;
}
int insert(Hash h, int pos, char *s, int p, int Max) /**哈希查找的插入实现 ,分别是哈希数组，数组位置，身份证号，数组最大大小, MAX 看到代码最后就明白了**/
{
    int i, posb = pos;             /**备份pos值方便双向平方查找**/
    for (i = 1;; i++)
    {
        if (strcmp(h[pos].phone, "") == 0) /**如果为pos的值空直接插入**/
        {
            strcpy(h[pos].phone, s);
            h[pos].num++;
            Max = max(Max, h[pos].num);
            break;
        }
        else
        {
            if (strcmp(h[pos].phone, s) == 0) /**不为空的话，就看看身份证号是不是想等**/
            {
                h[pos].num++;
                Max = maxInt(Max, h[pos].num);
                break;
            }
            else
            { //原p%2==1
                if (i % 2 == 1) pos = (posb + (i*i)) % p;  /**不相等 就找下一个位置 ，分别向后找一次和往前找一次，如此循环**/
                else
                {              //原i*i
                    pos = posb - ((i - 1)*(i - 1));
                    while (pos<0)
                        pos += p;
                }
            }
        }
    }
    return Max;
}
void initial(Hash h, int p) /**把哈希数组初始化 （初始化的动词英文忘记咋写了。。。。）**/
{
    int i;
    for (i = 0; i<p; i++)
    {
        h[i].phone[0] = '\0';
        h[i].num = 0;
    }
}
int main(){


    int Max = 0;
    int n;  /**总数 N 然后就开始找 大于N的最小素数了**/
    scanf("%d", &n); /**输出中把\n也输入进去 避免下面输入会出现奇葩的事情**/
    int p = nextprime(2 * n); /**突然想起来 每次输入的都是俩电话号码，所以 电话号码最大数是2*n**/
    Hash h = (Hash)malloc(p*sizeof(struct Node));/**建立哈希数组**/
    initial(h, p);
    char phone[15];
    char phone1[15];
    while (n--)
    {
        scanf("%s %s", phone, phone1);
        Max = insert(h, deal(phone, p), phone, p, Max);
        Max = insert(h, deal(phone1, p), phone1, p, Max);
    }
    
    int i, num = 0;
    char *Minstr = NULL;
    for (i = 0; i<p; i++)
    {
        if (h[i].num == Max)
        {
            if (Minstr == NULL) Minstr = h[i].phone;
            else Minstr = minstr(Minstr, h[i].phone);
            num++;
        }
    }
    printf("%s %d", Minstr, Max);
    if (num>1) printf(" %d", num);
    system("PAUSE");//结束不退出
}

#define _CRT_SECURE_NO_WARNINGS  //避免scanf报错
#include <stdio.h>
#include <malloc.h>
void main()
{
    int i, j, m, n, *ns = NULL, *cn = NULL, sum = 0;
    printf("请输入总金额m及零钱种类n："), scanf("%d", &m), scanf("%d", &n);
    printf("请分别输入%d种零钱的面额：\n", n);
    if (!(ns = (int *)malloc(sizeof(int)*n))) return 1;
    if (!(cn = (int *)malloc(sizeof(int)*n))) return 1;
    for (i = 0; i<n; i++) scanf("%d", &ns[i]);
    //------------考虑输入面额顺序不定，先对面额进行降序排列（如按照降序输入，该段可删除）
    for (i = 0; i<n; i++)
    for (j = i + 1; j<n; j++)
    if (ns[j]>ns[i]) ns[j] ^= ns[i], ns[i] ^= ns[j], ns[j] ^= ns[i];

    for (i = 0; i<n; i++)//贪心算法，从最大面额开始
    if (m >= ns[i])
        cn[i] = m / ns[i], m = m%ns[i], sum += cn[i], printf("%d元%d张 ", ns[i], cn[i]);
    printf("\n最少使用零钱%d张\n", sum);
    system("PAUSE");//结束不退出
}

#define _CRT_SECURE_NO_WARNINGS  //避免scanf报错
#include "stdio.h"
#include "stdlib.h"

int power(int x, int n)
{
    int result;
    if (n == 1)
        return x;
    if (n % 2 == 0)
        result = power(x, n / 2) * power(x, n / 2);
    else
        result = power(x, (n + 1) / 2) * power(x, (n - 1) / 2);
    return result;
}

void main()
{
    int x = 5;
    int n = 3;
    printf("power(%d,%d) = %d \n", x, n, power(x, n));
    system("PAUSE");//结束不退出
}

#define _CRT_SECURE_NO_WARNINGS  //避免scanf报错
#include "stdio.h"
#include "stdlib.h"
#include "assert.h"
#include "string.h"

void print_arr(int *arr, int len)
{
    int i = 0;

    for (i = 0; i < len; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

void merge(int *arr, int low, int mid, int hight, int *tmp)
{
    assert(arr && low >= 0 && low <= mid && mid <= hight);

    int i = low;
    int j = mid + 1;
    int index = 0;

    while (i <= mid && j <= hight)
    {
        if (arr[i] <= arr[j])
            tmp[index++] = arr[i++];
        else
            tmp[index++] = arr[j++];
    }

    while (i <= mid) //拷贝剩下的左半部分
        tmp[index++] = arr[i++];

    while (j <= hight) //拷贝剩下的右半部分
        tmp[index++] = arr[j++];

    memcpy((void *)(arr + low), (void *)tmp, (hight - low + 1) * sizeof(int));

}

void mergesort(int *arr, int low, int hight, int *tmp)
{
    assert(arr && low >= 0);
    int mid;
    if (low < hight)
    {
        mid = (hight + low) >> 1;
        mergesort(arr, low, mid, tmp);
        mergesort(arr, mid + 1, hight, tmp);
        merge(arr, low, mid, hight, tmp);
    }
}
//只分配一次内存，避免内存操作开销
void mergesort_drive(int *arr, int len)
{
    int *tmp = (int *)malloc(len * sizeof(int));
    if (!tmp)
    {
        printf("out of memory\n");
        exit(0);
    }
    mergesort(arr, 0, len - 1, tmp);
    free(tmp);
}

void main()
{
    int data[10] = { 8, 7, 2, 6, 9, 10, 3, 4, 5, 1 };
    int len = sizeof(data) / sizeof(data[0]);
    mergesort_drive(data, len);
    print_arr(data, len);
    system("PAUSE");//结束不退出
}

#define _CRT_SECURE_NO_WARNINGS  //避免scanf报错
#include <stdio.h>
//设置一个数组，数组的下标表示集合中的元素，所以数组只用下标为1，2，3的空间
int set[5];
//i代表数组下标，n表示集合中最大的元素值
void PowerSet(int i, int n){
    //当i>n时，说明集合中所有的元素都做了选择，开始判断
    if (i>n) {
        for (int j = 1; j <= n; j++) {
            //如果树组中存放的是 1，说明在当初尝试时，选择取该元素，即对应的数组下标，所以，可以输出
            if (set[j] == 1) {
                printf("%d ", j);
            }
        }
        printf("\n");
    }
    else{
        //如果选择要该元素，对应的数组单元中赋值为1；反之，赋值为0。然后继续向下探索
        set[i] = 1; PowerSet(i + 1, n);
        set[i] = 0; PowerSet(i + 1, n);
    }
}
void main() {
    int n = 3;
    for (int i = 0; i<5; i++) {
        set[i] = 0;
    }
    PowerSet(1, n);
    system("PAUSE");//结束不退出
}

Fab(n)= Fab(n-1)+Fab(n-2)
Fab(1)=Fab(2)=1;

static int GetFab(int n)
        {
            if (n == 1) return 1;
            if (n == 2) return 1;
            return GetFab(n - 1) + GetFab(n - 2);
        }

static int[] fab = new int[6];
static int GetFabDynamic(int n)
        {
            if (n == 1) return fab[1] = 1;
            if (n == 2) return fab[2] = 1;
            if (fab[n] != 0)//如果存在，就直接返回。
            {
                return fab[n];
            }
            else //如果不存在，就进入递归，并且记录下求得的值。
            {
                return fab[n] = GetFabDynamic(n - 1) + GetFabDynamic(n - 2);
            }
        }

static int[] size = new int[] { 3, 4, 7, 8, 9 };// 5件物品每件大小分别为3, 4, 7, 8, 9 且是不可分割的  0-1 背包问题
        static int[] values = new int[] { 4, 5, 10, 11, 13 };//// 5件物品每件的价值分别为4, 5, 10, 11, 13
        static int capacity = 16;
        static int[,] dp = new int[6, capacity + 1];
        static int knapsack(int n, int w)
        {
            if (w < 0) return -10000;
            if (n == 0) return 0;
            if (dp[n, w] != 0)
            {
                return dp[n, w];
            }
            else
            {
                return dp[n, w] = Math.Max(knapsack(n - 1, w), knapsack(n - 1, w - size[n - 1]) + values[n - 1]);
                  /*                 
                 * knapsack(n,w) 指在前N件物品在W剩余容量下的最大价值。
                 * 这个公式的意思是，对于某一件物品，
                 * 1、如果选择装进去，那么，当前价值=前面的n-1件物品在空位w - size(n)下的最大价值（因为空位需要留出，空位也隐含了价值）。
                 * 再加上这件物品的价值。等于 knapsack(n - 1, w - size[n - 1]) + values[n - 1]
                 * 2、 如果我们选择不装进去，那么，在n-1物品的情况下空位仍然在，当前价值 = 前面n-1件物品在空位w下的最大价值。
                 * 等于knapsack(n - 1, w)
                 * 注意：随着演算，某一情况下的价值不会一成不变。
                 * 此时我们做出决策：到底是在装入时的价值大，还是不装入时的价值大呢？我们选择上面两种情况中值较大的。并记录在案。
                 * 最后dp[N,M]就是我们要求的值。
                 */            }
        }