递归，到处都是递归----小话c语言(10)

[Mac 10.7.1 Lion Intel-based x64 gcc4.2.1]

Q：递归的本质是什么？

A：递归能够运行，在于宇宙万物之间的联系和计算机最终指令的完备性。换句话说，如果一个公式的参数不能和参数相关的公式有联系，那么递归对它无解。

Q：举些例子说明递归的无处不在吧。

A：比如需要计算一个数组中最大的数值。

int find_max(int arr[], int size)

如果从递归的角度，求一个数组中最大的值被分解为求第一个数和剩下一个数组中最大值比较得到的最大值。

所以代码如下：

#include <stdio.h>

#define PRINT_D(intValue)   printf(#intValue" is %d\n", (intValue));
#define MAX(a, b)   ((a) > (b) ? (a) : (b))

int find_max(int arr[], int size)
{
    if(size == 1)
        return arr[0];
    if(size == 2)
        return MAX(arr[0], arr[1]);
    return MAX(arr[0], find_max(arr + 1, size - 1));
}

int main()
{
    int arr[] = {34, 2, 190, 345, 23};
    int max_ret = find_max(arr, sizeof(arr) / sizeof(arr[0]));
    PRINT_D(max_ret)
    
    return 0;
}

运行结果：

同理，求数组中最小值，求字符串的长度，数组中所有元素的和等等也类似。

Q： 字符串反转可以使用递归么？

A： 是的。如果需要将一个字符串反转，可以这么思考：它将首先将第一个和最后一个字符反转，接着将中间的字符串反转，代码如下：

#include <stdio.h>

#define PRINT_STR(str)      printf(#str" is %s\n", (str));
#define SWAP(type, a, b)    {type temp = a; a = b; b = temp;}

void    reverse_str(char *str, int len)
{
    if(len <= 1)
        return;
    SWAP(char, str[0], str[len - 1]);
    reverse_str(str + 1, len - 2);
}

int main()
{
    char buf[] = "hello world";
    reverse_str(buf, strlen(buf));
    PRINT_STR(buf)
    return 0;
}

运行结果：

Q：将一个整形数的字符串形式输出，如何用递归？

A：可以将此整数模10，得到的数据最后输出；继续递归整数除以10剩下的数值。

#include <stdio.h>

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

int main()
{
    print_int(123);
    return 0;
}

执行结果：

同理，逆序输出，判断是否是回文也是类似的。

Q：输出一个整形对应二进制形式中含有位1的个数，如何用递归？

A：它的值可以看成：如果整数n是奇数，那么返回 n / 2二进制含有位1个数 + 1的和；如果是偶数，直接返回 n / 2二进制含有位1的个数；

代码如下：

#include <stdio.h>
#define PRINT_D(intValue)   printf(#intValue" is %d\n", (intValue));

int int_has_1_count(int n)
{
    if(n <= 1)
        return n % 2;
    if(n % 2 == 0)
        return int_has_1_count(n / 2);
    else
        return int_has_1_count(n / 2) + 1;
}

int main()
{
    PRINT_D(int_has_1_count(1099))
    return 0;
}

运行结果：

1099的二进制形式是： 10001001011,可以确定含有二进制位1的个数为5.

同理，二分查找，二叉树遍历等都类似。

Q：求一个数加上另一个数m的值，如何用递归？

A：将此过程分解为m次自增操作。如下示例：

#include <stdio.h>
#define PRINT_D(intValue)   printf(#intValue" is %d\n", (intValue));

int add_x(int *n, int add_num)
{
    if(add_num < 1)
        return *n;
    if(add_num == 1)
        return ++(*n);
    else
    {
        ++(*n);
        return add_x(n, add_num - 1);
    }
}

int main()
{
    int n = 12;
    PRINT_D(add_x(&n, 3))
    return 0;
}

运行结果：

类似，两个变量之间的操作都可以转换成更小的操作，看怎么使用更小的操作来实现大操作。

Q： 3个不同元素abc，输出排列方式组成的所有形式。比如， abc, acb, bca等等。

A：将输出的大过程看成需要输出此3个元素，小过程为输出一个元素，且只能输出一次。代码如下：

#include <stdio.h>
#define PRINT_D(intValue)   printf(#intValue" is %d\n", (intValue));

// a, b, c : the output char;
// print_count_a, print_count_b, print_count_c : can print count
// output: the output array
// output_index: current print index
void    print_abc_all_styles(char a, char b, char c, 
                             int print_count_a, 
                             int print_count_b,
                             int print_count_c,
                             char output[],
                             int  output_index)
{
    if(print_count_a + print_count_b + print_count_c == 0)
    {
        printf("%c%c%c", output[0], output[1], output[2]);
        printf("\n");
        return;
    }
    
    if(print_count_a == 1)
    {
        output[output_index] = a;
        --print_count_a;
        print_abc_all_styles(a, b, c, 
                             print_count_a, 
                             print_count_b, 
                             print_count_c,
                             output, output_index + 1);
        ++print_count_a;
        
    }
    if(print_count_b == 1)
    {
        output[output_index] = b;
        --print_count_b;
        print_abc_all_styles(a, b, c, 
                             print_count_a, 
                             print_count_b, 
                             print_count_c,
                             output, output_index + 1);
        ++print_count_b;
    }
    if(print_count_c == 1)
    {
        output[output_index] = c;
        --print_count_c;
        print_abc_all_styles(a, b, c, 
                             print_count_a, 
                             print_count_b, 
                             print_count_c,
                             output, output_index + 1);
        ++print_count_c;
    }
}

运行结果：

对于abc这样的排列，或者aabc, abbc, aabbcc这样的排列或者组合，都可以用类似方法解决；

一个更一般的代码：

#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#define PRINT_D(intValue)   printf(#intValue" is %d\n", (intValue));

static  bool    isExist(const char *str, const int str_size, char ch)
{
    int i;
    for(i = 0; i < str_size; ++i)
    {
        if(str[i] == ch)
            return true;
    }
    return false;
}

void    print_abc_all_styles(const char *elements,  // be outputed elements
                             int max_print_count,   // max printed elements
                             char output[],     // output string
                             const int  output_size,  // output string size
                             int  output_index) // current output index
{
    int i;
    if(max_print_count == 0)
    {
        int i = 0;
        for(; i < output_size; ++i)
            printf("%c", output[i]);
        printf("\n");
        return;
    }
    
    for(i = 0; i < strlen(elements); ++i)
    {
        if(!isExist(output, output_index, elements[i]))
        {
            output[output_index] = elements[i];
            --max_print_count;
            print_abc_all_styles(elements, max_print_count,
                                 output, output_size, output_index + 1);
            ++max_print_count;
        }
    }
}

int main()
{
    char buf[4] = {0};
    print_abc_all_styles("abc", 3, buf, 3, 0);
    return 0;
}

Q： 如何输出一段字符串？

A： 先输出第一个，然后将剩下的当做字符串输出；

Q：如何下载文件？

A：先下载前1个字节，后面继续使用前面的方式下载；

Q：如何飞到月球？

A：先飞第一段，然后飞剩下所有段；

Q：如何做一盘菜？

A：先做菜的第一部分，然后做剩下的部分；

Q：如何追小妞？

A：第一天采用某种方法和她相遇搭讪，后来采用类似但可能不同的方式找她搭讪，做该做的事，最后搞定她。不过涉及到情感问题，不能像计算机一样，它是不稳定的。

Q：如何回家？

A：做一件离你家更近的事情，然后继续做类似的事情；

Q：如何上网？

A：先做上网的第一个准备工作，然后做剩下的工作；

Q：如何吃饭？

A：先吃第一口，之后吃完所有该吃的饭。

Q：如何写代码？

A：先写第一句，后面写完所有的代码；

Q： .........

A： .........

总之，不要认为回答的太简单，而在于递归本来就很简单。

xichen

2012-5-17 11:50:49