引言：迭代与递归对于初学者可能会是一个难点，
现在就准备讲解这个。

一.预备知识——函数

直接点来说C语言里的函数和数学里的函数完全是两回事，
C语言里的函数就是子程序，功能划分更细小的一段代码。
为什么需要函数？目的就是为了编写程序能够更方便。你
要是问为什么，那我举个例子，你平时用得最多的两个函
数scanf和printf ，这个其实就是别人编写好的函数，在
你包含了相应的头文件（也就是函数声明）以后，你要用
的时候只要按这两个函数的要求传递参数就能实现你所需
要的功能了。有了函数这个东西，你就不需要在你每次要
进行输入输出的时候，都要自己重复地写详细的实现过程，
而只需要简单地调用一下已经写好的代码。

以下就是一个简单的函数例子：

int isPrime(int n)//判断n是不是素数，如果是就返回1
{
    int a;
    for(a=2; a<n; ++a)  // a用于试除，注意a<n
    {
        if(n % a == 0)  // 余数为0就是说不是素数了
        {
            break;
        }
    }
    if(a < n)
    {
        return 0;
    }
    return 1;
}

你写好这个函数以后，再需要判断一个数是不是素数的话，
很简单，只要：

int a;
scanf("%d", &a)
if(isPrime(a))
{
    printf("yes");
}
else
{
    printf("no");
}

怎么样，够简单吧，和和printf输出结果一样那么轻松。


二.迭代

迭代的一个经典例子是斐波那契数列，这个数列是这样定义的：
       f(n-1) + f(n-2)    (n>2)
f(n)={
       1                  (1<=n<=2)
意思是说这个数列形如：1,1,2,3,5,8,13,21,34,55,........
前两个是1，下一个数是它前面两个数的和。
现在问题来了，输入一个n，计算出这个数列的第n项是什么数。
例如输入：6
    输出：8

你也许会想，既然是算第n个，那就要推算n次了吧，用个for循环
就行了，然后你可能写出以下代码：

#include <stdio.h>
int main(void)
{
    int n, s;
    scanf("%d", &n);         // 输入要计算的n
    for(int a=2; a<=n; ++a)  // a控制循环次数
    {
        //
    }
    printf("%d\n", s);       // s用来保存结果
    return 0;
}

好了，写到这里你多数都会卡住了，因为如果只用这些变量，
根本不足以去计算。为此，从这个数列的定义观察，其中有：
f(n) = f(n-1) + f(n-2)
如果用数组实现，那么就很直观了。在假设输入的n最大是100
的情况下，你可能写出如下代码：

#include <stdio.h>
int main(void)
{
    int n;
    int f[100] = {0,1};
    scanf("%d", &n);         // 输入要计算的n
    for(int a=2; a<=n; ++a)  // a控制循环次数
    {
        f[a] = f[a-1] + f[a-2];
    }
    printf("%d\n", f[n]);    // f[n]就是结果
    return 0;
}

运行结果是正确的，还不错吧！不过，你会不会想，计算这个
可不可以不用数组呢？这个数组很浪费空间啊。为了确定能不
能把这个数组去掉，你需要分析一下每一次计算的时候，使用
了这个数组的哪些元素。很明显，只使用了f[a],f[a-1],f[a-2]
再之前的就没有再使用了，要计算下一个数，只需要知道上一
个数和上上个数。也就是说计算过程只需要用三个变量就可以
了。我们声明为nLL,nL,s，分别是上上个数、上一个、和计算
中的结果。代码可以改写为：

#include <stdio.h>
int main(void)
{
    int n;
    int nLL=0,nL=1,s=1;      // 初始化
    scanf("%d", &n);         // 输入要计算的n
    for(int a=2; a<=n; ++a)  // a控制循环次数
    {
        s = nLL + nL;        // 计算当前的f(n)
        nLL = nL;            // 原来的上一个要变成上上一个
        nL = s;              // 当前的结果要变成上一个
    }
    printf("%d\n", s);       // s用来保存结果
    return 0;
}

怎么样，迭代也不难吧。
迭代习题：http://yzfy.org/bbs/viewthread.php?tid=138
本文章版权属于http://yzfy.org雨中飞燕之家论坛所有

三.递归

本点是令新手头痛的一大问题，这里也会重点解释。

经典题目1:输入一个字符串，然后反序输出。

常规的解法是写入到一个char数组，然后从后向前输出。
但是，如果你要用递归来解的话，思路就完全不同了。
首先，由于是字符输入，我们需要一个一个字符来处理，
所以可以选择用getchar()函数。然后，怎么去构造这个
递归函数呢？首先，我们假设这个函数已经写好了，名字
是fs()，它能完成这个功能。现在，我们写一个名字是f
的函数，要调用它来完成整个功能（当然你不能直接把所
有东西都交给它啊，只是假设）。

f函数运行的时候，需要读取字符和输出字符，你可以这样
想，读取一个字符，然后把剩下的交给fs函数，由fs函数
把剩下的字符读取并且反向输出，最后你再把你自己读取的
字符输出来，不就完成了么？
假如输入"abcd"，你读取了第一个字符'a'，然后剩下的
由fs函数来处理，fs函数处理后输出反序的结果"dcb"后，你
再输出你所读取的字符'a'，最后就是"dcba"，大功告成。

假想代码如下：

void f()
{
    int c = getchar();   //记录下输入的第一个字符
    fs();  //让这个假想的函数来完成剩下的字符反转
    putchar(c);    //最后输出自己所记录下来的字符
}

现在你需要考虑一个问题：输入的那个字符如果是'\n'，
就表示那一行已经输入结束了，就不需要再调用fs函数了，
要不然你就不知道fs函数会干出些什么事情了，所以还得
像下面这样补上一个判断语句：

void f()
{
    int c = getchar(); //记录下输入的第一个字符
    if(c!='\n')fs();   //如果输入没有结束就让这个假想的函数来完成剩下的
    putchar(c);        //最后输出自己所记录下来的字符
}

好了，f函数也写好了。然后你就发现问题了，f和fs不就是
在完成同一个功能么？你所写的f函数就是假想的fs函数所
完成的功能了，所以你只需要把fs改成f，现在你就真正
大功告成了：

#include <stdio.h>
void f()
{
    int c = getchar(); //记录下输入的第一个字符
    if(c!='\n')f();    //让这个函数来完成剩下的字符反转
    putchar(c);        //最后输出自己所记录下来的字符
}
int main(void)
{
    f();  //调用这个函数
    return 0;
}

怎么样，运行一下试试吧，看看你理解了多少了。
假如输入abc回车，我们来看看详细是怎么运行的：
main调用f，第1层:
{
    先接收了一个'a'，再调用f:
    {
        接收了一个'b'，再调用f:
        {
            接收了一个'c'，再调用f:
            {
                接收了一个'\n'，结束
            }
            输出接收的'c'，结束
        }
        输出接收的'b'，结束
    }
    输出接收的'a'，结束
}


经典题目2:斐波那契数列
这个的题目和之前的那题一样，输入一个n，
计算出这个数列的第n项是什么数。
如果用递归的方法，思考的方法也是差不多，先假设这个函数
已经完成了，名字是fib(n)，你自己要编写的函数名字是f(n)，
为了计算f(n)的结束，你需要知道它前两项的结果，这个不就
很简单吗？只要调用fib函数就能得到结果了，所以就可以写出：

int f(n)
{
    return fib(n-1) + fib(n-2);
}

是不是很简单？先别急，现在你可要考虑特别的情况了。如果要
计算f(2)或者f(1)，那么会进行fib(2-2)也就是fib(0)的计算，
可是这个是没有定义的，不应该要让fib函数去计算它。由这个
数列定义可以知道f(1)=f(2)=1，所以我们可以简单地加一个语句
以避免出现计算fib(0)甚至fib(-1)的情况：

int f(n)
{
    if(n<=2)return 1;
    return fib(n-1) + fib(n-2);
}

现在这个f函数就完成了，结果同样，f函数和fib函数其实是一样的，
所以你就可以把f改成fib，然后写上main函数：

#include <stdio.h>
int fib(n)
{
    if(n<=2)return 1;
    return fib(n-1) + fib(n-2);
}
int main(void)
{
    int n;
    scanf("%d", &n);      //输入
    printf("%d", fib(n)); //计算并输出
    return 0;
}

怎么样？还算可以吧？慢慢理解一下吧:)