首页 » 开发 » 递归

递归

递归(Recursion)。算法中的递归指算法直接或间接调用自己。某些定义是递归的,如阶乘函数的定义:

int factorial(int n)
{
    if(n == 0) return 1;
    return (n * factorial(n-1));
}

如著名的斐波拉契数列:

int fib(int n)
{
    if(n == 0 or n == 1) return n;
    return (fib(n - 1) + fib(n - 2));
}

如链表或二叉树的节点定义:

struct node {
    node* _next;
};

大多数递归算法都可以用非递归算法重写,这样可以大大的提高运行效率,但非递归代码通常比递归代码难以理解。上述的阶乘和斐波拉契数列用非递归算法写:

int factorial2(int n)
{
    int ret = 1;
    for(int i = n; i > 0; --i) {
        ret *= i;
    }
    return ret;
}

int fib2(int n)
{
    if(n == 0 or n == 1) return n;

    int j = 0, k = 1, ret = 0;
    for(int i = 2; i < n+1; ++i) {
        ret = j + k;
        j = k;
        k = ret;
    }
    return ret;
}

二分搜索的递归与非递归实现算法:

int bsearch(int key, int* arr, int bg, int ed) 
{
    if(bg > ed) return -1; 

    int mid = (bg + ed) / 2;
    if(key == arr[mid]) return mid;

    if(key > arr[mid]) return bsearch(key, arr, mid+1, ed);
    else return bsearch(key, arr, bg, mid-1);
}

int bsearch2(int key, int* arr, int bg, int ed) 
{
    int mid;
    while(bg <= ed) {
        mid = (bg + ed)/2;
        if(key == arr[mid]) return mid;
        if(key > arr[mid]) {
            bg = mid+1;
        } else {
            ed = mid-1;
        }   
    }   
    return -1; 
}

某些问题比较容易用非递归算法代替递归算法(如二叉树的遍历),但某些递归算法用非递归算法实现则非常困难,如典型的汉诺塔问题。汉诺塔问题是有3根柱子A、B、C,有一堆大小不同的盘子,最初盘子从小到大放在A柱上,目标是把A柱的所有盘子移动到C柱上,要求每次只能移动一个盘子,且放置盘子时必须大盘在下小盘在上,移动过程中,盘子可以放在A、B、C任一柱上。汉诺塔的递归式求解:

void hanoi(int n, char from, char aux, char to)
{
    if(n == 1) {
        printf("move disk %d from %c to %c\n", n, from, to);
        return ;
    }

    /* move n-1 disk FROM from TO aux HELPED BY to */
    hanoi(n-1, from, to, aux);

    /* move disk n FROM from TO to directly */
    printf("move disk %d from %c to %c\n", n, from, to);

    /* move n-1 disk FROM aux TO to HELPED BY from */
    hanoi(n-1, aux, from, to);
}

测试当有4个盘子时的移动情况:

hanoi(4, 'A', 'B', 'C');

/* output: */
move disk 1 from A to B
move disk 2 from A to C
move disk 1 from B to C
move disk 3 from A to B
move disk 1 from C to A
move disk 2 from C to B
move disk 1 from A to B
move disk 4 from A to C
move disk 1 from B to C
move disk 2 from B to A
move disk 1 from C to A
move disk 3 from B to C
move disk 1 from A to B
move disk 2 from A to C
move disk 1 from B to C

分享

0