tceic.com
学霸学习网 这下你爽了
相关标签
当前位置:首页 >> 学科竞赛 >>

Recursive Functions计算机竞赛


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.


推荐相关:

NSRecursiveLock,递归锁

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


exponential functions and recursive rules.

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


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 ...


Google C++ Style Guide_IT/计算机_专业资料

Google C++ Style Guide_IT/计算机_专业资料。Google C++ Style Guide Revision ...such; for example, virtual and recursive functions are not normally inlined...


ExperimentReport-User difined function

上海理工大学计算机工程学院 实验报告 实验名称 课程名称 User-Defined Functions ...Realize it using recursive function. 2. Experiment Environment(Software, ...


ACM程序设计竞赛例题

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


Recursive Calls

Recursive Calls_IT/计算机_专业资料。Recursive calls are only allowed for subprocedures. A recursive call is one where procedureRecursive...


ACM国际大学生程序设计竞赛指南

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


用哈夫曼树实现图像压缩_IT/计算机_专业资料

//static functions of HTN static HTN *htn_new(char ch, int count) { ...} static void htn_print_recursive(HTN *htn, int depth) { int i; if(...


pci configure space_计算机硬件及网络_IT/计算机_专业资料

? ? ? ? 4 5 6 7 8 3.1 "Brute Force" Scan 3.2 Recursive Scan 3....If bit 7 of this register is set, the device has multiple functions; ...

网站首页 | 网站地图
All rights reserved Powered by 学霸学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com