关于并行递归程序等价变换的若干研究

一般而言,要把并行递归程序转化为等价的尾递归程序(它直接对应于循环迭代程序)是十分困难的。本文指出,具有某种性质的两类(分别称为α类和β类)并行递归程序可以转化为等价的尾递归程序,从而具有较高的时空运行效率。     

基于栈结构的孔明棋算法研究

孔明棋是一种玩法简单,但其中变化无数的益智游戏。对孔明棋求解问题进行分析,提出了基于回溯思想的递归和非递归算法,运行结果表明了算法的有效性。文章还围绕栈在存储数据、消解递归等方面的应用对两个算法的优缺点进行了比较分析,递归算法结构清晰,但递归调用次数多;而非递归算法借助程序栈,将程序向循环转化,降低了时间复杂度,但算法难以分析和理解。因此在求解实际问题时可以采用递归思想来分析,然后借助栈用非递归来实现算法。     

以问题结构为基础的递归程序设计

对递归程序的结构进行了较为深入的研究,提出了递归程序的更一般结构,根据此结构,给出了复杂的递归疸的程序设计方法,根据此方法,可方便地写出较为复杂的递归问题的递归程序,从而提高设计递归程序的效率。     

递归程序结构研究

对递归程序的结构进行了较为深入的研究 ,提出了递归树的概念 ,给出了递归程序的一般结构 ,把递归分为简单链结构、树状结构、复杂链结构三种情况 ,据此 ,给出了复杂的递归问题的程序设计方法 ,根据此方法 ,可方便地写出较为复杂的递归问题的递归程序 ,从而提高设计递归程序的效率。     

应用递归神经网络学习周期运动吸引子轨迹

采用递归神经网络学习非线性周期运动的吸引子轨迹．网络的拓扑结构基于非线性系统的状态空间表达式,网络权值通过时序反向传播算法调整．探讨了不同样本轨迹和网络结构对递归神经网络预测性能的影响．神经网络的性能评估建立在多条测试样本轨迹的基础上,可以更为客观地评价递归神经网络预测性能．对van der Pol方程的仿真结果表明:网络的泛化能力对训练样本轨迹的依赖性较强,从不同训练轨迹上得到的递归神经网络性能差异较大;需要选择合适的递归神经网络结构参数以提高神经网络的泛化能力．     

基于轨迹的归纳程序综合

本文讨论了NDIPS系统中基于轨迹的归纳程序综合方法。该方法对问题求解机制产生的或手工给出的程序执行轨迹,使用匹配识认算法找出其递归关系,进而生成目标程序,文章从理论和实现上对这种方法进行了探讨,用hanoi程序的归纳综合为例展示了方法的使用。     

递归程序的正确性证明

<正> 4.1 引言 许多程序设计语言(例如,ALGOL、PL/1、LISP)是允许程序员用来编写递归程序的;即作为其计算时调用它自身部分的程序(递归地)恰好与一个非递归程序一样可调用辅程序。这种递归程序在处理具有递归定义数据结构比如表格或树状是非常有用的。这种递归程序是以一种语言比如LISP为基础的,它主     

递归程序设计方法的分析探讨

递归是设计程序的一种重要方法,文中对递归的定义及递归的基本条件进行了分析,给出了递归程序设计的基本方法,并结合数据结构中二叉树遍历和单链表结点输出的实例进行了验证,最后对递归程序进行了深度分析,说明了递归是一种有效的程序设计方法。     

数据结构下的程序递归算法设计及应用

在数据结构基础上使用程序递归算法设计是目前进行软件开发应用最广泛的方法.使用递归算法进行程序编写可以减少很多操作细节,从而简化程序编写,而且递归算法结构简单且清晰,易读性比较强,最大的优势递归算法正确率高、验证比较方便.对递归程序算法的应用进行了分析,并探讨了递归算法的实现策略.     

基于C语言的递归函数教学方法探讨

本文从实际教学出发,首先讨论了递归的基本条件,总结出递归程序的设计方法,然后详细分析递归程序的执行过程并给出了递归程序的一般结构,最后让学生自己分析汉诺塔问题并动手写程序,在教学中取得了较好的效果。     

Visual representations for recursion

Visualcode is a visual notation that uses coloured expressions and graphical environments to describe the execution of Scheme programs. RainbowScheme is a program visualization system which is designed to produce visualcode representations of step-by-step execution of Scheme programs. This article presents a new approach of teaching recursion using visualcode and RainbowScheme. Experimental evaluation indicates that viewing RainbowScheme-produced visual traces and requiring students to use visualcode to generate visual evaluation steps of recursive programs can enhance the learners' ability to evaluate recursive programs as well as to solve recursive programming problems.     

Execution traces and programming-language semantics

The trace of a program-a string representing the sequence of statements executed for a particular input- and a program's trace language-all such strings-are considered as an expression of the control-flow possibilities inherent in the program. It is shown that, for a language like Turing's, programs always have trace languages that are context-sensitive but not always context-free. Such low-level languages lose most of their computing power if restricted to context-free traces. For languages in which individual statements are more powerful than those of a Turing machine, the trace languages may fail to be recursive, but the context-sensitive behavior may be regained by slightly altering the idea of a trace. In any case, it is also shown that it is impossible to effectively identify programs that have trace languages more restrictive than the widest class available in the programming language.     

Compositional learning of mutually recursive procedural systems

This paper presents a compositional approach to active automata learning of Systems of Procedural Automata (SPAs), an extension of Deterministic Finite Automata (DFAs) to systems of DFAs that can mutually call each other. SPAs are of high practical relevance, as they allow one to efficiently learn intuitive recursive models of recursive programs after an easy instrumentation that makes calls and returns observable. Key to our approach is the simultaneous inference of individual DFAs for each of the involved procedures via expansion and projection: membership queries for the individual DFAs are expanded to membership queries of the entire SPA, and global counterexample traces are transformed into counterexamples for the DFAs of concerned procedures. This reduces the inference of SPAs to a simultaneous inference of the DFAs for the involved procedures for which we can utilize various existing regular learning algorithms. The inferred models are easy to understand and allow for an intuitive display of the procedural system under learning that reveals its recursive structure. We implemented the algorithm within the LearnLib framework in order to provide a ready-to-use tool for practical application which is publicly available on GitHub for experimentation.

     

递归程序设计的公式化方法

如果在设计递归程序时首先写出它的递归公式,那么编码过程会大大简化,而且得到的程序具有极好的可读性。这一思想有助于递归程序的标准化,并具有很大的普遍性。     

Evolving Recursive Programs by Using Adaptive Grammar Based Genetic Programming

Genetic programming (GP) extends traditional genetic algorithms to automatically induce computer programs. GP has been applied in a wide range of applications such as software re-engineering, electrical circuits synthesis, knowledge engineering, and data mining. One of the most important and challenging research areas in GP is the investigation of ways to successfully evolve recursive programs. A recursive program is one that calls itself either directly or indirectly through other programs. Because recursions lead to compact and general programs and provide a mechanism for reusing program code, they facilitate GP to solve larger and more complicated problems. Nevertheless, it is commonly agreed that the recursive program learning problem is very difficult for GP. In this paper, we propose techniques to tackle the difficulties in learning recursive programs. The techniques are incorporated into an adaptive Grammar Based Genetic Programming system (adaptive GBGP). A number of experiments have been performed to demonstrate that the system improves the effectiveness and efficiency in evolving recursive programs. Communicated by: William B. Langdon An erratum to this article is available at .     

递归函数的应用

递归函数独特的运算方式，使其在人工智能和各种事务处理过程中有着广泛的应用，因而成为一个重要的研究课题。文中以迷宫、汉诺塔等为例．根据计算机堆栈原理，具体讨论了用递归函数解题的方法和技巧。给出了递归函数调用时利用变量传递解决复杂问题的实例，展示了递归算法在解决非数值运算问题中的独特解题方式和效果。讨论表明，在求解人工智能和各种事务处理问题中．递归函数中合理地利用变量传递可有效地完成求解任务和提高程序的品质。     

An introduction to inductive programming

The research field of inductive programming is concerned with the design of algorithms for learning computer programs with complex flow of control (typically recursive calls) from incomplete specifications such as examples. We introduce a basic algorithmic approach for inductive programming and illustrate it with three systems: dialogs learns logic programs by combining inductive and abductive reasoning; the classical thesys system and its extension igor1 learn functional programs based on a recurrence detection mechanism in traces; igor2 learns functional programs over algebraic data-types making use of constructor-term rewriting systems. Furthermore, we give a short history of inductive programming, discuss related approaches, and give hints about current applications and possible future directions of research. A short, non-technical version of this paper appears in C. Sammut, editor, Encyclopedia of Machine Learning, Springer–Verlag, forthcoming. The paper was written while the first author was on sabbatical in 2006/2007 at Sabancı University in İstanbul, Turkey.     

Computer generation of robot dynamics equations and the related issues

Two programs have been developed using the computer algebra system REDUCE to generate the dynamics equations of motion for robot manipulators. One of these programs is based on a Lagrange formulation and the other utilizes a recursive Newton-Euler formulation. Both programs produce equivalent scalar symbolic expressions for the generalized actuator forces, but the program based on the recursive Newton-Euler formulation is more efficient for the generation of equations. These programs have been used to generate the dynamics equations of manipulators with as many as six degrees of freedom. The efficiency of computing forces using the generated scalar symbolic expressions is compared with the efficiency of a numerical algorithm (implemented in FORTRAN '77) based on the recursive Newton-Euler formulation. Force computation by the method of symbolic equations is shown to be more efficient than the numerical recursive Newton-Euler algorithm. The technique of symbolic equations is also better adapted to multi-CPU processing.