lanxicy.com

第一范文网 文档专家

第一范文网 文档专家

Recursive Functions A definition that defines an object in terms of itself is said to be recursive. This theoretical mathematical topic serves as an introduction to recursive programming (which is supported by Pascal, but not by most BASICs). It also provides a framework for analyzing algorithms (determining the running time and/or space required) which contain loops or recursive sections. Many expressions may be defined recursively in a very simple and elegant manner. The art of recursive thinking is an important skill. Applications of recursion appear in many areas of mathematics (factorials, compound interest, difference equations, etc.) In this round recursive relationships will be shown not in the context of a programming language but usually in functional notation from mathematics or in an algorithmic description. References Roberts, Eric S. Thinking Recursively, Wiley (1986). Rohl, J.S. Recursion via Pascal, Cambridge University Press (1984). Wirth, Niklaus. Algorithms + Data Structures = Programs, Prentice-Hall (1976), Chapter 3.

Sample Problems Consider the following recursive algorithm for painting a square: 1. Given a square. 2. If the length of a side is less than 2 feet, then stop. 3. Divide the square into 4 equal size squares (i.e., draw a “plus” sign inside the square). 4. Paint one of these 4 small squares. 5. Repeat this procedure (start at step 1) for each of the 3 unpainted squares. If this algorithm is applied to a square with a side of 16 feet (having a total area of 256 sq. feet), how many square feet will be painted? In the first pass, we get four squares of side 8. One is painted; three are unpainted. Next, we have 3*4 squares of side 4: three are painted (area=3*42), nine are not. Next, we have 9*4 squares of side 2: nine are painted (area = 9*22), 27 are not. Finally, we have 27*4 squares of side 1: twenty-seven are painted. Therefore, the total painted is 1*82 + 3*42 + 9*22 + 27*12 = 175.

Evaluate f(12, 6), given: f(x,y) = +2 ? f(x-y,y-1) x+y when x>y otherwise

Evaluate the function as follows: f(12, 6) = f(6, 5)+2 = (f (1, 4)+2)+2 = f(1, 4)+4 = (1+4)+4 =9 Working backwards, we get f(0)= 1 f(1) = 2 f(2) = f(f(0))+1 = f(1)+1 = 2+1 = 3 f(3) = f(f(1))+1 = f(2)+1 = 3+1 = 4 f(4) = f(f(2))+1 = f(3)+1 = 4+1 = 5 f(5) = f(f(3))+1 = f(4)+1 = 5+1 = 6 f(6) = f(f(4))+1 = f(5)+1 = 6+1 = 7 Ackerman’s Function is infamous for its potential growth. In fact, we don’t have room here to give a full explanation of the problem. For details, refer to the 1981-82 ACSL All-Star Contest. By evaluating A(1,0), A(1,1), A(1,2) and A(1,3), we see that in general, A(1, x)=2+x. If we evaluate A(2,0), A(2,1), …, we see that in general, A(2,x)=2x+3. To solve our problem, we substitute x=3 and we get an answer of 9.

Find f(6), given:

f(x) =

?

f (f (x-2))+1 2 1

when x>1 when x=1 when x=0

One of the best known recursive functions, Ackerman’s Function, is defined below. Evaluate A(2, 3). A(M,N) =

?

N+1 if M=0 A(M-1, 1) if M?0, N=0 A(M-1, A(M, N-1)) if M?0, N?0

Challenge for the bored: Evaluate A(n, m) in terms of n and m.

相关文章:

- ACM程序设计竞赛例题
- ACM程序设计
*竞赛*例题_*计算机*软件及应用_IT/*计算机*_专业资料。备战 ACM 资料 一:...(最短路径)*Recursive*Search Techniques (回溯搜索技术) Minimum Spanning Tree ...

- ACM国际大学生程序设计竞赛指南
- ACM国际大学生程序设计
*竞赛*指南_IT/*计算机*_专业资料。ACM的一些信息ACM...(最短路径)*Recursive*Search Techniques (回溯搜索技术) Minimum Spanning Tree ...

- 计算机全英班09期末
*计算机*全英班09期末 华南理工大学历年历届C++ 期末考试试卷试题、答案及复习资料大全...B)*Recursive**functions*are the*functions*that call themselves directly. C)...

- 2015数据结构实验手册_电脑基础知识_IT/计算机_专业资料
- 特别是多文件大型工程的编 程;了解 ACM
*竞赛*的赛题,掌握参加 ACM*竞赛*的基本...Step 2. Write*recursive*version*functions*of inOrder, preOrder and postOrder...

- exponential functions and recursive rules.
- exponential
*functions*and*recursive*rules._高一数学_数学_高中教育_教育专区。国外指数函数教学设计exponential*functions*and*recursive*rules. In this lesson make ...

- NSRecursiveLock,递归锁
- NS
*Recursive*Lock,递归锁_*计算机*软件及应用_IT/*计算机*_专业资料。NS*Recursive*Lock,递归锁 NS*Recursive*Lock,多次调用不会阻塞已获取该锁的 线程。 NS*Recursive*Lock *the...

- ACM程序设计-Operand-Code the Tree
- 百度文库 专业资料 IT/
*计算机**计算机*软件及应用...Obviously, the dividing process is*recursive*. As ...*functions*are always valid.Display a blank line ...

- 17review(Recursion)_计算机软件及应用_IT/计算机_专业资料
- 17review(Recursion)_
*计算机*软件及应用_IT/*计算机*_专业资料。Chapter 17 Recursion...(TRUE)*Recursive**functions*are always simpler than non-*recursive**functions*. ...

- Recursive Patterns OF SNOBOL
- In our previous discussion of
*recursive**functions*, we said they work because successive calls present the function with progressively simpler problems, until ...

- 二叉树的部分算法
- Uses: The
*functions**recursive*_insert,*recursive*_height */ { if (sub_root == NULL) sub_root = new Binary_node<Entry>(x); else if (*recursive*_...

更多相关标签:

- Unary Primitive Recursive Functions
- Learning recursive functions
- Analysis of Parallelism in Recursive Functions on Recursive Data Structures
- 计算机竞赛(小学组)计算机基本常识
- Value functions satisfy recursive relationships V
- From recursive to IR-recursive functions
- Tutte Polynomials and Related Asymptotic Limiting Functions for Recursive Families of Graph
- Models of Computation Primitive Recursive Functions
- Defining Recursive Functions in IsabelleHOL
- A note on recursive functions
- 汉中事业单位考试职业能力倾向测验答题技巧：资料分析图形类题型解题方法
- 基督城女子高中学生住宿
- 东华《护理伦理学》16春平时作业1
- 奥鹏西工大16春《基础会计学》在线作业
- 职业高中计算机班网络期中试卷