迭代和函数的递归的学习

对于模块化程序的初步了解

一个真正的程序里面白喊自定义函数，也包含对应的头文件，还有函数定义界面。于是创建了个简单的加法函数。
函数的声明

#ifndef __ADD_H__
#define __ADD_H__

//函数的声明
int Add(int x, int y);

#endif

我将这个声明放在目录为add.h的文件下，其中的

#ifndef __ADD_H__
#define __ADD_H__

#endif

作用是为了防止函数连续被调用时整个函数的定义段被连续搬运，导致主程序的代码量过大。函数的调用原理是，讲函数定义目录下的代码经过头文件搬运到需要用的地方，然后执行。
函数的定义

int Add(int x, int y)
{
    return (x + y);
}

放在目录为add.c的目录下，将对应功能的函数放在具有提示意义的目录下面，能够与他人更好的配合，具有可读性。
主函数

#include <stdio.h>
#include "add.h"
int main()
{
    int a = 15;
    int b = 25;
    printf("sum=%d\n",Add(a, b));

    return 0;
}

引用自定义函数的头文件时，用的是双引号 "" 。

最简单的递归

#include <stdio.h>
int main()
{
    printf("haha\n");
    main();
    return 0;
}//递归常见的错误，栈溢出，stack overflow

这是一个没有限制条件的递归，程序运行一会儿就会自己停止，并且弹出警告窗口，原因是，程序运行的时候，会将运行时产生的局部变量存在名为堆栈的一个内存区域，这个没有限制的递归，不断的调用自身，不断的打印“haha”，就会将堆栈占满。
而这个程序也让人能理解，递归，就是函数对于自身的调用，用现在的网络流行语，俗称套娃。

设计一个递归函数 分别打印出1234里的1 2 3 4

void print(int n)
{
    if (n > 9)
    {
        print(n / 10);
    }
    printf("%d ", n % 10);

}
#include <stdio.h>
int main()
{
    int num = 0;
    scanf("%d", &num);
    print(num);
    return 0;
}

第一次要使用递归进行实现某一个功能其实是 很没有头绪的，尽管听老师讲完了 ，程序也跟着打了出来，也看着调试一步步的调了，眼看着代码一行一行的走，尤其是函数里面的调用，到了最后一层，不满足调用条件的时候，程序运行窗口就一个一个的把字符打印出来了，我前期是比较没有理解，程序执行到这个地方是怎么一层一层的返回去的，就是忘记了程序执行到了哪里，老师画图讲解之后，才算是明白，一层一层的进来，也是要一层一层的出去。当最后一层不再满足条件执行完毕弹出之后，弹出到上一层之后，继续执行下一条语句，以此类推。

不创建临时变量，求字符串长度

先是写一个能实现求字符串从长度的函数，不考虑递归
最简单的当然是直接使用库函数计算字符串长度

#include <string.h>
int main()
{
        strlen();
}

接下来用自定义函数

int my_strlen(char* str)
{
    int count = 0;
    while (*str != '\0')
    {
        count++;
        str = str + 1;
    }
    return count;
}

整个字符串是无法直接被函数调用的，只能讲字符串的地址作为指针变量，指向字符串的第一个字符，调用进入函数之中，每次用完之后+1，直到看到‘\0’字符，字符串的长度计算停止。count就作为一个计数，记录字符串的长度。可是我们需要的是一个不用临时变量的函数实现这一功能。

#include <stdio.h>
int my_strlen(char* str)
{
    if (*str != '\0')
        return 1+my_strlen(str + 1);
    else
        return 0;
}//未使用临时变量进行计数，实现了求字符串长度
int main()
{
    char arr[] = "bit";
    int len = my_strlen(arr);//传送过去的是数组第一个元素的地址，并不是整个数组
    printf("len = %d\n", len);
    return 0;
}

递归还是一样，用画图的方法解释起来更容易理解，将程序执行的过程可视化，增强理解，有一定的限制条件，而且每一层调用函数都在使得限制条件更加接近不满足if语句，最终能够停止递归过程。俗称停止套娃。

递归和迭代 求阶乘

当理解了前面两个递归的例子之后，我也独立写出了这个求阶乘的递归代码，大概思路为，想要求出n！，先要求出（n-1）！，想要求出（n-1）！，先要求出（n-2）！，快进到想要求出2！，就先求出1！，所以还是对自身的不断调用，代码如下：

#include <stdio.h>
int Fac1(int n)
{
    int num = 1;
    int i = 0;
    for (i = 1; i <= n; i++)
    {
        num = i * num;
    }
    return num;
}
int Fac2(int n)
{
    int ret = 1;
    if (n != 0)
         ret = n * Fac2(n - 1);
    else
        return ret;
}
int main()
{
    int n = 0;
    scanf("%d", &n);
    printf("%d!=%d\n",n, Fac1(n));
    printf("%d!=%d\n",n, Fac2(n));
    return 0;
}

其中也用了个for循环写了另一个函数实现目的。

求斐波那契数列的第n个

斐波那契数列，1 1 2 3 5 8...简单的说，就是想知道第n个，就得先知道第n-1个和第n-2个，要知道第n-1个和第n-2个，就得知道第n-2和n-3个，第n-3和n-4个...以此类推，可是递归求第n个，需要运算的次数，就是2^n+2^(n-1)+...+2^2+2次运算，当求到第40个以上的时候，程序已经有了很明显的等待，需要等待才能出结果，计算的次数其实已经很大，n每+1，运算次数就会多出两倍，运算时间也会多出两倍，代码如下：

#include <stdio.h>
int Fib1(int n)
{
    if (n <= 2)
        return 1;
    else
        return  Fib1(n - 1) + Fib1(n - 2);
}
int Fib2(int n)
{
    int a = 1, b = 1, c=0;
    int i = 0;
    if (n > 2)
    {
        for (i = 3; i <= n; i++)
        {
            c = a + b;
            a = b;
            b = c;
        }
        return c;
    }
    else
        return 1;
}
int main()
{
    int n = 0;
    scanf("%d", &n);
    int f2 = Fib2(n);
    printf("第%d个斐波那契数列：%d\n", n, f2);
    int f1 = Fib1(n);
    printf("第%d个斐波那契数列：%d\n", n, f1);
    return 0;
}

所以以上代码中还有一个，不用递归，直接用迭代实现的函数，一运行就能看到，两个函数实现目标的时间差，所以当，递归之中函数调用的次数过大时，运算量巨大，就很有必要使用其他手段实现目标。