C 中的复合函数

Question

如果我有一个函数组合 f(f(f(f(x)))) 我如何将其编写为 C 中的函数？可以用递归算法写吗？

例如，如果我们有以下函数会发生什么:

f(x)=cosa*X1+cosb*X2 where x=(X1,X2)

Answer 1

这是我的一个示例玩具程序，这是一个将迭代与头尾递归进行比较的练习。

对这个问题进行了一些修改，它重新应用函数“wibble”N 次，并通过结构数组聚合 X0,X1，通过 reapply_f 迭代和递归函数构建系列。重构尾部调用优化版本，将代码变异回看起来像迭代。(仅使用 typedef 数组会出现问题，您无法从函数返回它，并且在传递给函数调用时没有按值调用语义。)

输出:

Iterative Series Technique
    f0 = f(0.100000,0.900000)
    f1 = f(1.000000,-0.800000)
    f2 = f(0.200000,1.800000)
    f3 = f(2.000000,-1.600000)

Head Recursive Series Technique
    f0 = f(0.100000,0.900000)
    f1 = f(1.000000,-0.800000)
    f2 = f(0.200000,1.800000)
    f3 = f(2.000000,-1.600000)

Tail Recursive Series Technique
    f0 = f(0.100000,0.900000)
    f1 = f(1.000000,-0.800000)
    f2 = f(0.200000,1.800000)
    f3 = f(2.000000,-1.600000)

Optimised Tail Recursive Series Technique
    f0 = f(0.100000,0.900000)
    f1 = f(1.000000,-0.800000)
    f2 = f(0.200000,1.800000)
    f3 = f(2.000000,-1.600000)

Tidied Optimised Tail Recursive Series Technique
    f0 = f(0.100000,0.900000)
    f1 = f(1.000000,-0.800000)
    f2 = f(0.200000,1.800000)
    f3 = f(2.000000,-1.600000)

和 C，显示了迭代和递归代码的相似性:

#include <stdio.h>
#include <stdlib.h>

typedef struct aggregate {
    double X[2];
} aggregate;

void display_series(int n, aggregate series[]) {
    for (int i=0; i<=n; i++) {
        printf( "    f%d = f(%f,%f)\n", i, series[i].X[0], series[i].X[1]);
    }
    putchar( '\n');
}

void init_series(int n, aggregate series[]) {
    series[0].X[0] = 0.1; series[0].X[1] = 0.9;
    for (int i=1; i <= n; i++) {
        series[ i].X[0] = 0.0; series[ i].X[1] = 0.0;
    }
}

aggregate wibble( const aggregate in) {
    aggregate out;
    out.X[0] = in.X[0] + in.X[1];
    out.X[1] = in.X[0] - in.X[1];
    return out;
}

aggregate reapply_f_iterative(int n, aggregate (*f)(), aggregate series[]) {
    for (int i=1; i <= n; i++) {
        series[ i] = (*f)( series[ i-1]);
    }
    return series[n];
}

aggregate reapply_f_head_recursive(int n, aggregate (*f)(), aggregate series[]) {
    if (n>0) {
        reapply_f_head_recursive( n-1, f, series);
    series[n] = (*f)( series[n-1]);
    }
    return series[n];
}

aggregate reapply_f_tail_recursive( int applied, int limit, aggregate (*f)(), aggregate series[]) {
    if (applied >= limit) {
        return series[ applied];
    }
    series[applied+1] = (*f)( series[ applied]);
    return reapply_f_tail_recursive( ++applied, limit, f, series);
}

aggregate reapply_f_optimised_tail_recursive( int applied, int limit, aggregate (*f)(), aggregate series[]) {
RESTART:
    if (applied >= limit) {
        return series[ applied];
    }
    series[applied+1] = (*f)( series[ applied]);
    ++applied;
    goto RESTART;
}

aggregate reapply_f_tidied_optimised_tail_recursive( int applied, int limit, aggregate (*f)(), aggregate series[]) {
    for( ; applied < limit; ++applied) {
        series[ applied+1] = (*f)( series[ applied]);
    };
    return series[ applied];
}



int main (int argc, char **argv) {

    /* series 0..N */
    size_t N = 3;
    if (argc == 2) {
        N = strtol( argv[ 1], NULL, 0);
    }
    aggregate *series = calloc( N+1, sizeof( aggregate));

    printf( "Iterative Series Technique\n");
    init_series( N, series);
    (void) reapply_f_iterative( N, &wibble, series);
    display_series( N, series);

    printf( "Head Recursive Series Technique\n");
    init_series( N, series);
    (void) reapply_f_head_recursive( N, &wibble, series);
    display_series( N, series);

    printf( "Tail Recursive Series Technique\n");
    init_series( N, series);
    (void) reapply_f_tail_recursive( 0, N, &wibble, series);
    display_series( N, series);

    printf( "Optimised Tail Recursive Series Technique\n");
    init_series( N, series);
    (void) reapply_f_optimised_tail_recursive( 0, N, &wibble, series);
    display_series( N, series);

    printf( "Tidied Optimised Tail Recursive Series Technique\n");
    init_series( N, series);
    (void) reapply_f_tidied_optimised_tail_recursive( 0, N, &wibble, series);
    display_series( N, series);
}