1.递归定义

函数自己调用和调用其他函数并没有本质的不同。我们把一个直接调用自己或通过一系列的调用语句间接地调用自己的函数，称作递归函数。
切记，每个递归定义必须至少有一个条件，当满足这个条件时递归不再进行，即函数不再调用自身而是返回值。

迭代和递归的区别是：迭代使用的是循环结构，递归使用的是选择结构。

  1. //迭代
  2. #include <stdio.h>
  4. int main()
  5. {
  6.     int i;
  7.     int a[40];
  9.     a[0] = 0;
  10.     a[1] = 1;
  11.     printf("%d %d ", a[0], a[1]);
  13.     for( i=2; i < 40; i++ )
  14.     {
  15.         a[i] = a[i-1] + a[i-2];
  16.         printf("%d ", a[i]);
  17.     }
  19.     return 0;
  20. }
//递归
#include <stdio.h>

int Fib(int i)
{
    if( i < 2 )
    {
        return i == 0 ? 0 : 1;
    }

    return Fib(i-1) + Fib(i-2);
}

int main()
{
    int i;
    for( i=0; i < 40; i++ )
    {
        printf("%d ", Fib(i));
    }

    return 0;
}

2.实例分析

题目要求：编写一个递归函数，实现将输入的任意长度的字符串反向输出的功能。例如输入字符串FishC,则输出字符串ChsiF。

void print()
{
    char a;
    scanf(“%c”, &a);
if( a !=‘#’)  print();
if( a !=‘#’)  printf(“%c”, a);
}

折半查找算法的递归实现
从算法的折半查找的过程我们不难看出，这实际上也是一个递归的过程：因为每次都将问题的规模减小至原来的一半，而缩小后的子问题和原问题类型保持一致。


#include <stdio.h>

int bin_search( int key[], int low, int high, int k )
{
    int mid;

    if( low > high )
    {
        return -1;
    }
    else
    {
        mid = (low + high) / 2;

        if( key[mid] == k )
        {
            return mid;
        }

        if( k > key[mid] )
        {
            return bin_search( key, mid+1, high, k );    // 在序列的后半部分查找
        }
        else
        {
            return bin_search( key, low, mid-1, k );    // 在序列的前半部分查找
        }

    }
}

int main()
{
        int str[11] = {1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89};
        int n, addr;

        printf("请输入待查找的关键字: ");
        scanf("%d", &n);

        addr = bin_search(str, 0, 10, n);
        if( -1 != addr )
        {
                printf("查找成功，可喜可贺，可口可乐! 关键字 %d 所在的位置是: %d\n", n, addr);
        }
        else
        {
                printf("查找失败!\n");
        }

        return 0;
}