1

我正在阅读有关相互递归的内容。在几乎所有材料中，确定整数是偶数还是奇数的例子都是问题？

int is_even(unsigned int n)
{
    if (n==0) return 1;
    else return(is_odd(n-1));
}

int is_odd(unsigned int n)
{
    return (!iseven(n));
}

显然，上述问题可以使用模数运算符以更简单的方式解决。

另一个例子是找出一个人是女性还是男性的问题。这也可以在不使用递归的情况下以更简单的方式解决。

那么相互递归只是理论上的还是在任何地方我都可以使用它来实际使我的解决方案比使用任何其他技术更简单？

你能举一个这样的例子来帮助我吗？

4

3 回答 3

3

相互递归不是很常见，但有时很有用。使用“递归下降”方法解析文本是一种实用的设置，您可以在其中找到它。

http://en.m.wikipedia.org/wiki/Recursive_descent_parser

于 2013-07-15T06:43:57.107 回答
1

我通常有一个用例是当我编写一个程序来玩游戏时。在这种情况下，您通常会使用递归来遍历游戏树来计算最佳移动。

虽然它通常可以非常简单地完成而无需相互递归，但当每个参与者的逻辑足够复杂以保证其自己的功能时，以这种方式编码会很有帮助，并且有足够多不同的参与者试图打造一个巨人功能一团糟。

于 2013-07-15T06:58:37.447 回答
0

真的很晚的帖子，一个例子是快速选择算法，如果你的枢轴策略是中位数算法，因为中位数枢轴方法调用快速选择来计算每个中位数的 n/5 中位数5 元素组。

另一个流行的方法是在 Scheme 中编译 s-expression 的 eval-apply 方法，Matt Might 的以下实现：

 eval takes an expression and an environment to a value
(define (eval e env) (cond
  ((symbol? e)       (cadr (assq e env)))
  ((eq? (car e) 'λ)  (cons e env))
  (else              (apply (eval (car e) env) (eval (cadr e) env)))))

; apply takes a function and an argument to a value
(define (apply f x)
  (eval (cddr (car f)) (cons (list (cadr (car f)) x) (cdr f))))

; read and parse stdin, then evaluate:
(display (eval (read) '())) (newline)
于 2019-05-10T22:29:55.323 回答