仅使用递归执行此操作

Question

编写一个递归函数 evenDigits，它接受整数参数 n 和 returns 一个仅包含 n 中偶数位的新整数，顺序相同。如果 n 不包含任何偶数位，return 0.

例如evenDigits(8342116)的调用应该return8426，evenDigits(35179)的调用应该return0.

Answer 1

为了实现递归，你需要应用一个Y Combinator。

确保对复杂问题实施最终递归优化，Y Combinator 的简单实施通常不会这样做。根据您的编译器供应商，可能有低级挂钩到适当的阶段 2 和 3 优化步骤，然后您需要将其集成到您的实际递归实现中。

假设您已经将递归实现为宏的一部分 letfn，您可以像这样解决手头的问题：

(fn f (input)
  (letfn g (remainder shift result)
    (let (next_even_digit next_remainder) (fetch_next_even_digit remainder shift)
      (if next_even_digit
        (g next_remainder (* shift 10) (+ result (* shift next_even_digit)))
        result))))

我将 fetch_next_even_digit 的简单实现留给 reader。

Answer 2

这是我的五分钱。:)

#include <stdio.h>

int evenDigits( int n )
{
    const int Base = 10;

    int digit = n % Base;

    int even = digit % 2 == 0;

    if ( !even ) digit = 0;

    return ( n /= Base ) == 0 ? digit 
                              : ( even ? Base : 1 ) * evenDigits( n ) + digit;
}

int main(void) 
{
    printf( "evenDigits( 8342116 ) = %d\n", evenDigits( 8342116 ) );
    printf( "evenDigits( -8342116 ) = %d\n", evenDigits( -8342116 ) );
    printf( "evenDigits( 35179 ) = %d\n", evenDigits( 35179 ) );
    printf( "evenDigits( -35179 ) = %d\n", evenDigits( -35179 ) );

    return 0;
}

程序输出为

evenDigits( 8342116 ) = 8426
evenDigits( -8342116 ) = -8426
evenDigits( 35179 ) = 0
evenDigits( -35179 ) = 0

Answer 3

size_t implementation(size_t remainder, size_t shift, size_t result) {
    // long form:
    // while (remainder != 0 && remainder % 2 != 0)
    while (remainder % 2 != 0) {
        remainder /= 10;
    }
    if (remainder == 0) {
        return result;
    }
    size_t next_digit = (remainder % 10);
    size_t next_result = result + (next_digit * shift);
    return implementation(
            remainder / 10,
            shift * 10,
            next_result);
}

size_t even_digits(size_t input) {
    return implementation(input, 1, 0);
}

仅使用递归执行此操作

do this using recursion only

c

recursion

function

definition