Re: коммивояжёp

From

Ivan Boldyrev (2:5080/1003)

To

Val Krylov

Date

2003-01-17T10:21:48Z

Area

RU.ALGORITHMS

From: Ivan Boldyrev <boldyrev@dataeast.ru>

Val Krylov <Val.Krylov@p27.f1900.n5030.z2.fidonet.org> writes:

>     Любая pекypсия пpедставима итеpацией. Любая итеpация пpедставима
> pекypсией.  Элементаpный алгоpитм вида "нахождение стpоки в тексте",
> напpимеp, достаточно ясно пpедставим и в итеpативной, и в
> pекypсивной фоpме, но в pекypсивном слyчае он сводится лишь к тоннам
> мyсоpа на стеке. Мне нет необходимости пpиводить алгоpитмы к менее
> эффективным фоpмам, благо не пpиходится кодить на Хаскеле.

Делать поиск подстроки лениво, вот вам поиск символа.

/* Хорошая такая хвостовая рекурсия */
const char * findchar(const char *str, char c) {
    if (*str) {
        if (c==*str)
            return str;
        else
            return findchar(++str, c);
    } else
        return 0;
}

findchar:
        pushl   %ebp
        movl    %esp, %ebp
        movl    8(%ebp), %edx
        movb    12(%ebp), %al
        movb    (%edx), %cl
        testb   %cl, %cl
        je      .L2
        cmpb    %cl, %al
        je      .L6
        movsbl  %al,%eax
        incl    %edx
        movl    %eax, 12(%ebp)
        movl    %edx, 8(%ebp)
        popl    %ebp
        jmp     findchar
        .p2align 4,,7
.L6:
        movl    %edx, %eax
.L1:
        popl    %ebp
        ret
        .p2align 4,,7
.L2:
        xorl    %eax, %eax
        jmp     .L1

И кто же вам, уважаемый, в стеке-то намусорил? Руки или компилятор?

-- 
Ivan Boldyrev
PGP fp: 3640 E637 EE3D AA51 A59F  3306 A5BD D198 5609 8673

                                                   По дороге в не туда...
--- ifmail v.2.15dev5
 * Origin: (http://news.cca.usart.ru/) USURT's FidoNET<-> (2:5080/1003@fidonet)