是否有递归函数调用另一个函数（该函数也调用第一个函数）的示例？
示例：
function1()
{
//do something
function2();
//do something
}
function2()
{
//do something
function1();
//do something
}
相互递归在解析数学表达式（和其他语法）的代码中很常见。基于以下语法的递归下降解析器自然会包含相互递归：
expression-terms-term-factor-primary-expressionexpression
+ terms
- terms
terms
terms
term + terms
term - terms
term
factor
factor * term
factor / term
factor
primary
primary ^ factor
primary
( expression )
number
name
name ( expression )
正确的术语是“相互递归”。
http://en.wikipedia.org/wiki/Mutual_recursion
该页面上有一个示例，我将在此处用 Java 重现：
boolean even( int number )
{
if( number == 0 )
return true;
else
return odd(abs(number)-1)
}
boolean odd( int number )
{
if( number == 0 )
return false;
else
return even(abs(number)-1);
}
其中abs( n ) 表示返回数字的绝对值。
显然这效率不高，只是为了证明一点。
一个例子可能是国际象棋等游戏程序中常用的最小最大算法。从游戏树的顶部开始，目标是找到下面级别的所有节点的 maximum 值，其值定义为其下节点值的 minimum，其值定义为作为低于该值的最大值，其值...
我能想到两个常见的相互递归来源。
考虑一个抽象语法树（AST），它在每个节点中保存位置信息。该类型可能如下所示：
type Expr =
| Int of int
| Var of string
| Add of ExprAux * ExprAux
and ExprAux = Expr of int * Expr
编写操作这些类型值的函数的最简单方法是编写相互递归函数。例如，查找自由变量集的函数：
let rec freeVariables = function
| Int n -> Set.empty
| Var x -> Set.singleton x
| Add(f, g) -> Set.union (freeVariablesAux f) (freeVariablesAux g)
and freeVariablesAux (Expr(loc, e)) =
freeVariables e
考虑一个打开、关闭或暂停的状态机，并带有启动、停止、暂停和恢复的指令（F# 代码）：
type Instruction = Start | Stop | Pause | Resume
状态机可以写成相互递归函数，每个状态有一个函数：
type State = State of (Instruction -> State)
let rec isOff = function
| Start -> State isOn
| _ -> State isOff
and isOn = function
| Stop -> State isOff
| Pause -> State isPaused
| _ -> State isOn
and isPaused = function
| Stop -> State isOff
| Resume -> State isOn
| _ -> State isPaused
这有点做作并且效率不高，但是您可以使用计算斐波那契数的函数来完成此操作，如下所示：
fib2(n) { return fib(n-2); }
fib1(n) { return fib(n-1); }
fib(n)
{
if (n>1)
return fib1(n) + fib2(n);
else
return 1;
}
在这种情况下，如果语言支持memoization
，其效率可以显着提高在具有适当尾部调用的语言中，相互尾部递归是实现自动机的一种非常自然的方式。
这是我的编码解决方案。 对于使用相互递归执行
*/-()Flow:: expression -> term -> factor -> expression
Calculator.h
#ifndef CALCULATOR_H_
#define CALCULATOR_H_
#include <string>
using namespace std;
/****** A Calculator Class holding expression, term, factor ********/
class Calculator
{
public:
/**Default Constructor*/
Calculator();
/** Parameterized Constructor common for all exception
* @aparam e exception value
* */
Calculator(char e);
/**
* Function to start computation
* @param input - input expression*/
void start(string input);
/**
* Evaluates Term*
* @param input string for term*/
double term(string& input);
/* Evaluates factor*
* @param input string for factor*/
double factor(string& input);
/* Evaluates Expression*
* @param input string for expression*/
double expression(string& input);
/* Evaluates number*
* @param input string for number*/
string number(string n);
/**
* Prints calculates value of the expression
* */
void print();
/**
* Converts char to double
* @param c input char
* */
double charTONum(const char* c);
/**
* Get error
*/
char get_value() const;
/** Reset all values*/
void reset();
private:
int lock;//set lock to check extra parenthesis
double result;// result
char error_msg;// error message
};
/**Error for unexpected string operation*/
class Unexpected_error:public Calculator
{
public:
Unexpected_error(char e):Calculator(e){};
};
/**Error for missing parenthesis*/
class Missing_parenthesis:public Calculator
{
public:
Missing_parenthesis(char e):Calculator(e){};
};
/**Error if divide by zeros*/
class DivideByZero:public Calculator{
public:
DivideByZero():Calculator(){};
};
#endif
===============================================================================
Calculator.cpp
//============================================================================
// Name : Calculator.cpp
// Author : Anurag
// Version :
// Copyright : Your copyright notice
// Description : Calculator using mutual recursion in C++, Ansi-style
//============================================================================
#include "Calculator.h"
#include <iostream>
#include <string>
#include <math.h>
#include <exception>
using namespace std;
Calculator::Calculator():lock(0),result(0),error_msg(' '){
}
Calculator::Calculator(char e):result(0), error_msg(e) {
}
char Calculator::get_value() const {
return this->error_msg;
}
void Calculator::start(string input) {
try{
result = expression(input);
print();
}catch (Unexpected_error e) {
cout<<result<<endl;
cout<<"***** Unexpected "<<e.get_value()<<endl;
}catch (Missing_parenthesis e) {
cout<<"***** Missing "<<e.get_value()<<endl;
}catch (DivideByZero e) {
cout<<"***** Division By Zero" << endl;
}
}
double Calculator::expression(string& input) {
double expression=0;
if(input.size()==0)
return 0;
expression = term(input);
if(input[0] == ' ')
input = input.substr(1);
if(input[0] == '+') {
input = input.substr(1);
expression += term(input);
}
else if(input[0] == '-') {
input = input.substr(1);
expression -= term(input);
}
if(input[0] == '%'){
result = expression;
throw Unexpected_error(input[0]);
}
if(input[0]==')' && lock<=0 )
throw Missing_parenthesis(')');
return expression;
}
double Calculator::term(string& input) {
if(input.size()==0)
return 1;
double term=1;
term = factor(input);
if(input[0] == ' ')
input = input.substr(1);
if(input[0] == '*') {
input = input.substr(1);
term = term * factor(input);
}
else if(input[0] == '/') {
input = input.substr(1);
double den = factor(input);
if(den==0) {
throw DivideByZero();
}
term = term / den;
}
return term;
}
double Calculator::factor(string& input) {
double factor=0;
if(input[0] == ' ') {
input = input.substr(1);
}
if(input[0] == '(') {
lock++;
input = input.substr(1);
factor = expression(input);
if(input[0]==')') {
lock--;
input = input.substr(1);
return factor;
}else{
throw Missing_parenthesis(')');
}
}
else if (input[0]>='0' && input[0]<='9'){
string nums = input.substr(0,1) + number(input.substr(1));
input = input.substr(nums.size());
return stod(nums);
}
else {
result = factor;
throw Unexpected_error(input[0]);
}
return factor;
}
string Calculator::number(string input) {
if(input.substr(0,2)=="E+" || input.substr(0,2)=="E-" || input.substr(0,2)=="e-" || input.substr(0,2)=="e-")
return input.substr(0,2) + number(input.substr(2));
else if((input[0]>='0' && input[0]<='9') || (input[0]=='.'))
return input.substr(0,1) + number(input.substr(1));
else
return "";
}
void Calculator::print() {
cout << result << endl;
}
void Calculator::reset(){
this->lock=0;
this->result=0;
}
int main() {
Calculator* cal = new Calculator;
string input;
cout<<"Expression? ";
getline(cin,input);
while(input!="."){
cal->start(input.substr(0,input.size()-2));
cout<<"Expression? ";
cal->reset();
getline(cin,input);
}
cout << "Done!" << endl;
return 0;
}
==============================================================
Sample input-> Expression? (42+8)*10 =
Output-> 500
自上而下的归并排序可以使用一对相互递归的函数来根据递归级别来交替归并的方向。
下面的示例代码中，a[]是要排序的数组，b[]是临时工作数组。对于合并排序的简单实现，每个合并操作将数据从 a[] 复制到 b[]，然后将 b[] 合并回 a[]，或者从 a[] 合并到 b[]，然后从 b[ 复制] 返回到[]。这需要 n·ceiling(log2(n)) 次复制操作。为了消除合并时使用的复制操作，可以根据递归级别交替合并方向，从a[]合并到b[]，从b[]合并到a[]，...，并切换到in将小运行的插入排序放在 [] 中，因为小运行的插入排序比合并排序更快。
在此示例中，MergeSortAtoA() 和 MergeSortAtoB() 是相互递归函数。
Java 代码示例：
static final int ISZ = 64; // use insertion sort if size <= ISZ
static void MergeSort(int a[])
{
int n = a.length;
if(n < 2)
return;
int [] b = new int[n];
MergeSortAtoA(a, b, 0, n);
}
static void MergeSortAtoA(int a[], int b[], int ll, int ee)
{
if ((ee - ll) <= ISZ){ // use insertion sort on small runs
InsertionSort(a, ll, ee);
return;
}
int rr = (ll + ee)>>1; // midpoint, start of right half
MergeSortAtoB(a, b, ll, rr);
MergeSortAtoB(a, b, rr, ee);
Merge(b, a, ll, rr, ee); // merge b to a
}
static void MergeSortAtoB(int a[], int b[], int ll, int ee)
{
int rr = (ll + ee)>>1; // midpoint, start of right half
MergeSortAtoA(a, b, ll, rr);
MergeSortAtoA(a, b, rr, ee);
Merge(a, b, ll, rr, ee); // merge a to b
}
static void Merge(int a[], int b[], int ll, int rr, int ee)
{
int o = ll; // b[] index
int l = ll; // a[] left index
int r = rr; // a[] right index
while(true){ // merge data
if(a[l] <= a[r]){ // if a[l] <= a[r]
b[o++] = a[l++]; // copy a[l]
if(l < rr) // if not end of left run
continue; // continue (back to while)
while(r < ee){ // else copy rest of right run
b[o++] = a[r++];
}
break; // and return
} else { // else a[l] > a[r]
b[o++] = a[r++]; // copy a[r]
if(r < ee) // if not end of right run
continue; // continue (back to while)
while(l < rr){ // else copy rest of left run
b[o++] = a[l++];
}
break; // and return
}
}
}
static void InsertionSort(int a[], int ll, int ee)
{
int i, j;
int t;
for (j = ll + 1; j < ee; j++) {
t = a[j];
i = j-1;
while(i >= ll && a[i] > t){
a[i+1] = a[i];
i--;
}
a[i+1] = t;
}
}