有没有一个递归函数的例子，其中调用另一个函数，而这个另一个函数也会调用第一个函数?
例子:
function1()
{
//do something
function2();
//do something
}
function2()
{
//do something
function1();
//do something
}
互递归的例子有哪些？
15
- Hannoun Yassir
2
5你刚刚提供了一个例子 :) 除非你指的是真实生活中的例子？ - Anthony Forloney
通用术语是“相互递归”，确实有很多情况下，函数调用可能会导致对该函数的嵌套调用。 - bobince
8个回答
28
互相递归在解析数学表达式（和其他语法）的代码中非常普遍。基于下面的语法的递归下降解析器将自然地包含互相递归：expression-terms-term-factor-primary-expression。
expression
+ terms
- terms
terms
terms
term + terms
term - terms
term
factor
factor * term
factor / term
factor
primary
primary ^ factor
primary
( expression )
number
name
name ( expression )
- lhf
1
2+1，我也在考虑这个问题。实际上，使用相互尾递归来实现自动机只是尾递归下降解析器的一种特殊情况，而尾递归下降解析器则是递归下降解析器的一种变体。 - Jörg W Mittag
19
这个术语的正确说法是相互递归。
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) 表示返回一个数的绝对值。
显然这不是高效的，只是为了阐述一个观点。
- Geoff
13
一个例子可能是在象棋等游戏程序中常用的minmax算法。从游戏树的顶部开始，目标是找到下一层所有节点中值的最大值，这些值的定义为下面节点的最小值，其值又定义为下面节点的最大值，其值又定义为下面节点的...
- I. J. Kennedy
5
我可以想到两种常见的相互递归的来源。
处理相互递归类型的函数
考虑一个在每个节点中保留位置信息的抽象语法树（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
- J D
4
这种方法有些牵强，效率也不高，但你可以通过一个计算斐波那契数列的函数来实现：
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;
}
在这种情况下，如果语言支持记忆化，它的效率可以显著提高。
- andand
3
相互递归不同于双重递归，该问题描述了相互递归。任何相互递归的函数集都可以通过内联代码简单地展开为单个递归函数。 - Geoff
你现在已经修复了，我的评论看起来有些不合适！ - Geoff
@Geoff：没问题...我有点冲动了，开始不加思考地写东西。 - andand
3
在具有正确尾调用的语言中，相互尾递归是实现自动机的一种非常自然的方式。
- Jörg W Mittag
2
这是我的编码解决方案。针对一个计算器应用程序，使用相互递归执行*、/、-操作。它还检查括号(())以决定优先顺序。
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
- Anurag Shinde
1
自顶向下的归并排序可以使用一对相互递归的函数，根据递归层次交替合并的方向。
在下面的示例代码中，a[]是要排序的数组，b[]是临时工作数组。对于归并排序的朴素实现，每个合并操作都会将数据从a[]复制到b[]，然后将b[]合并回a[]，或者从a[]合并到b[]，然后从b[]复制回a[]。这需要n · ceiling(log2(n))个复制操作。为了消除用于合并的复制操作，可以根据递归层次交替合并的方向，从a[]合并到b[]，从b[]合并回a[]，...，并在a[]中运行小型run时切换到原地插入排序，因为小型run上的插入排序比归并排序更快。
在此示例中，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;
}
}
- rcgldr
5
如果您能添加一些有关为什么需要/可能需要该选择的提示，我很乐意帮助您解决问题。 :) - Will Ness
我不熟练地阅读Java。你的技术是否与此相关（https://codereview.stackexchange.com/questions/12666/merge-sort-in-scheme），或者只是长度类似于2^n+1？换句话说，它解决了什么问题？ - Will Ness
@WillNess - 我更新了我的答案，加入了解释，并在示例代码中添加了插入排序以处理小的运行。 - rcgldr
好的，但是当你从b[]合并到a[]时，数组b[]仍然从左到右遍历吗？我认为“方向”意味着改变遍历的方向。 - Will Ness
@WillNess - 是的，对于归并排序算法来说，元素需要从左到右进行处理才能保证稳定性。至于“交替合并方向”：一种方向会将元素从a[]移动和合并到b[]中，而另一种方向则会将元素从b[]移动和合并到a[]中，合并之前或之后不进行任何复制步骤。 - rcgldr
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接