c 语言 - 递归函数 - 斐波那契数列

递归函数有三个充分条件：第一是 函数体 ，第二是 递归区间 ，第三个是 终止条件，

斐波那契数列

例：求斐波那契数列第 n 项。斐波那契数列的第一项和第二项是 1，后面每一项是前两项之和，即 1,1,2,3,5,8,13，。。。

下面程序采用直接递归调用：

#include <stdio.h>
long fib(int n)
{if(n == 0 || n == 1)
        return 1;
    else
        return (fib(n-1)+fib(n-2));
}
int main()
{
    int i;
for(i = 0;i < 8;i++)
        printf("%ld",fib(i));
    printf("\n");
return 0;
}

程序执行结果如下：

fs@ubuntu:~/qiang/digui$ ./digui1
1 1 2 3 5 8 13 21 

递归的条件：

上面已经简单提到，现在再说明一下

一个问题能否用递归来实现，看其是否有如下特点：

1、须有完成函数任务的语句。

例如：下面的代码定义了一个递归函数

#include <stdio.h>
void count(int val)
{if (val > 1)
        count(val - 1);
    printf("OK:%d\n",val);
}

该函数的任务是在输出设备上显示”ok: 整数值“。

2、一个任务是否能够避免递归调用的测试。

例如，上面的代码中，语句 ”if (val > 1)” 便是一个测试，如果不满足条件，就不进行递归调用。

3、一个递归调用语句

该递归调用语句的参数应该逐渐逼近不满足条件，以至最后断绝递归。

例如，上面的代码汇总，语句 “if(val > 1)” 便是一个递归调用，参数在渐渐变小，这话总发展趋势能使测试 “if (val > 1)” 最终不满足。

4,、先测试，后递归调用

在递归函数定义中，必须先测试，后递归调用。也就是说，递归调用是有条件的，满足了条件，才可以递归。

例如，下面的代码无限制的调用函数自己，造成无限制递归，终将使栈空间溢出；

#include <stdio.h>
void count(int val)
{count(val - 1);// 无限制递归
    if (val > 1)
        printf("OK:%d\n",val);
}

下面是完整程序：

#include <stdio.h>
void count(int val)
{if (val > 1)
        count(val - 1);
    printf("OK:%d\n",val);
}
int main()
{
    int n = 10;
count(n);
return 0;
}

程序执行结果如下：

fs@ubuntu:~/qiang/digui$ vi digui2.c
fs@ubuntu:~/qiang/digui$ gcc -o digui2 digui2.c 
fs@ubuntu:~/qiang/digui$ ./digui2
OK:1
OK:2
OK:3
OK:4
OK:5
OK:6
OK:7
OK:8
OK:9
OK:10