标签: mutual-recursion

我有一个程序,它产生一系列功能f,g如下所示:

step (f,g) = (newF f g, newG f g)

newF f g x = r (f x) (g x)
newG f g x = s (f x) (g x)

foo = iterate step (f0,g0)

其中R和S是一些无趣的功能f x和g x.我天真地希望,有foo是一个列表将意味着当我打电话的第n个f它不会重新计算(N-1)个f,如果它已经计算出它(如将如果发生f和g没有功能).有没有办法记住这一点而不会将整个程序拆开(例如评估f0和g0所有相关论点,然后向上工作)？

在某些编程语言中,尤其是在C语言中,存在具有函数声明的头文件.这些函数"标题"位于代码之前,并且在具有相互递归的情况下是必需的.当函数头放在头文件中时,它们还有助于链接多个C文件一起编译的情况.

我对C文件中函数头的理解是它们有助于编译,因为它们定义函数的类型,如果它在定义之前被调用.如果这是错误的,我会很高兴能够得到纠正和更好的信息,但这是我对它的理解.

所以我不明白,为什么其他语言 - 在这种情况下我单挑OCaml - 没有功能标题.在OCaml中,存在具有签名的模块,但是签名不允许您的函数实例化是相互递归的,即使给出了类型.为了在OCaml中进行相互递归,你需要使用"和"关键字,或者在另一个函数中本地定义一个函数(据我所知).

(* version 1 *)
let rec firstfun = function
  | 0 -> 1
  | x -> secondfun (x - 1)
and secondfun = function
  | 0 -> 1
  | x -> firstfun x

(* version 2 *)
let rec firstfun = function
  | 0 -> 1
  | x -> 
       let rec secondfun = function
         |0 -> 1
         | x -> firstfun x in
       secondfun (x - 1)

那么为什么会这样呢？它与多态性有关吗？有没有我不考虑的编译瓶颈？

如果我编写以下代码，JSLint 会抱怨在定义之前使用了'isOdd'。有没有办法编写相互递归的代码并且仍然取悦JSLint？

var isEven = function(n) {
    if (n === 0) {
        return true;
    }
    return isOdd(n - 1);
};

var isOdd = function(n) {
    if (n === 0) {
        return false;
    }
    return isEven(n - 1);
};

我的问题是与代码有一定的风格,非常类似于递归,但不是很那.引用维基百科时,递归是"定义函数的方法,其中定义的函数在其自己的定义中应用".类似地,相互递归应用另一个函数,该函数直接或间接地应用我们定义的函数.

问题是我正在考虑和处理的代码不使用相同的功能!它在另一个函数中使用相同的代码(作为方法或闭包).

这里的问题是,虽然我的代码是相同的,但功能却不是.看一下以下基本的相互递归示例:

def is_even(x):
    if x == 0:
        return True
    else:
        return is_odd(x - 1)

def is_odd(x):
    if x == 0:
        return False
    else:
        return is_even(x - 1)

这有点直观,非常明显地相互递归.但是,如果我将每个函数作为每次调用创建的内部函数包装起来,它就会变得不那么清晰:

def make_is_even(): 
    def is_even(x):
        if x == 0:
            return True
        else:
           return make_is_odd()(x - 1)
    return is_even

def make_is_odd(): 
    def is_odd(x):
        if x == 0:
            return False
        else:
            return make_is_even()(x - 1)
    return is_odd

def is_even2(x):
    return make_is_even()(x)

def is_odd2(x):
    return make_is_odd()(x)

忽略隐式记忆等优化,这会产生一系列不严格递归的函数调用,创建和调用各种新函数,而不必两次调用相同的函数.尽管如此,所有这些函数都遵循一个共同的模板,并且只是一遍又一遍地创建的相同函数(可能具有不同的自由变量).

而且,我们可以提出一个直接等价的(毕竟,类实际上只是闭包,正确;)使用类实现.这尤其重要,因为这种 …

我想知道是否存在一个非人为的例子,其中相互递归是问题的最优雅解决方案,并且它不能轻易地减少/内联到单个递归函数.

我已经知道这个例子(来自维基百科)

function even?(number : Integer)
    if number == 0 then
        return true
    else
        return odd?(abs(number)-1)

function odd?(number : Integer)
    if number == 0 then
        return false
   else
        return even?(abs(number)-1)

但严重的是,没有一个心智正常的人会以这种方式检查数字的平价.

我在这里检查了关于这个主题的上一个答案 - 是否有任何相互递归的例子？但没有一个答案是我正在寻找的.

我知道它在递归解析中很有用 - 可能是实现它的唯一逻辑方法,但我需要一个更清晰,更具体的例子(最好是数学例子).

谢谢你的帮助？

编辑:

由于显然每个互相递归函数的元组都可以简化为单个函数,我宁愿知道是否存在使用相互递归函数是最佳/最可读方式的情况.

我保留的一些遗留代码卡在无限循环中(因此我自己似乎在一个); 但是,我无法弄清楚为什么/如何.

这是应用程序的入口点,它实例化主窗体(frmCentral):

代码展览A.

public static int Main(string [] args)
{
    try
    {
        AppDomain currentDomain = AppDomain.CurrentDomain;

        currentDomain.UnhandledException += new UnhandledExceptionEventHandler(GlobalExceptionHandler);

        string name = Assembly.GetExecutingAssembly().GetName().Name;
        MessageBox.Show(string.Format("Executing assembly is {0}", name)); // TODO: Remove after testing <= this one is seen
        IntPtr mutexHandle = CreateMutex(IntPtr.Zero, true, name);
        long error = GetLastError();
        MessageBox.Show(string.Format("Last error int was {0}", error.ToString())); // TODO: Remove after testing <= this one is also seen

        if (error == ERROR_ALREADY_EXISTS)
        {
            ReleaseMutex(mutexHandle);

            IntPtr hWnd = FindWindow("#NETCF_AGL_BASE_", null);
            if ((int) …

我正在尝试在F#中创建一个简单的状态机,但是无法使用循环依赖的两个状态来工作.
我有这个州工厂:

open System
let createState produceInput stateSwitchRule nextState = 
    let rec stateFunc() = 
        match produceInput() with
        | x when x = stateSwitchRule -> printfn "%s" "Switching state"; nextState()
        | _  -> printfn "%s" "Bad input. Try again"; stateFunc()
    stateFunc

我用它来创建两个相互递归的状态:

let rec pongState() = createState Console.ReadLine "go to ping" pingState
      and pingState = createState Console.ReadLine "go to pong" (pongState())

[<EntryPoint>]
let main argv = 
    pingState()
    0

当调用pingState()并输入"go to pong"时,状态切换为pong.但是当调用输入"go to ping"时,抛出了一个空引用异常.
无论如何,选择的方法是否存在？或者我应该以不同的方式对其进行建模？

在一个在线课程中，Kyle Simpson 说下面的代码演示了在 javascript 中提升的必要性，因为如果没有提升，“其中一个函数总是会被声明为时太晚”。

a(1)  // 39

function a(foo){
  if (foo > 20) return foo
    return b(foo+2)
}

function b(foo){
  return c(foo) + 1
}

function c(foo){
  return a(foo*2)
}

但这工作得很好。

var a = function(foo){
  if (foo > 20) return foo
    return b(foo+2)
}

var b = function(foo){
  return c(foo) + 1
}

var c = function(foo){
  return a(foo*2)
}

a(1) // 39

那么故事是怎样的呢？抛开调用的方便和放置，还有没有需要吊装的情况？

我尝试使用归纳数据类型的语法,但它得到一条错误消息"互感类型必须编译为具有依赖消除的基本归纳类型".

下面是我尝试定义命题even和odd自然数的一个例子

mutual inductive even, odd
with even: ? ? Prop
| z: even 0
| n: ? n, odd n ? even (n + 1)
with odd: ? ? Prop
| z: odd 1
| n: ? n, even n ? odd (n + 1)

还有一个相关的问题:定义相互递归函数的语法是什么？我似乎无法在任何地方找到它.

我编写了以下函数来检查括号表达式的有效性:

let matched str =
    let rec matched' stack = function
        | "" -> isEmpty stack
        | str ->
            match first str with
            | '(' | '[' | '{' as p -> matched' (push p stack) (rest str)
            | ')' -> matchClosing '(' stack str
            | ']' -> matchClosing '[' stack str
            | '}' -> matchClosing '{' stack str
            | _ -> matched' stack (rest str)

    and matchClosing expected stack s =
        match peek stack with
        | Some c when …