当前位置:首页 >> 学科竞赛 >>

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 (whi

ch 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 ...
数据结构2013春季A卷
第 2 学期 开课学院: 计算机学院 课程号: ...10. The primary ADT access functions used to ...3. (8p)Write a recursive function named small...
计算机全英班09期末
计算机全英班09期末 华南理工大学历年历届C++ 期末考试试卷试题、答案及复习资料大全...B) Recursive functions are the functions that call themselves directly. C)...
exponential functions and recursive rules.
exponential functions and recursive rules._高一数学_数学_高中教育_教育专区。国外指数函数教学设计exponential functions and recursive rules. In this lesson make ...
大学计算机基础类术语
recursive 递回 recursively 递回地 recycler 回收站 redefinition 重复定义 ...functions 终止函式 termination handler 终止处理常式 terms of use 使用规定 ...
pp顾问考题_计算机软件及应用_IT/计算机_专业资料
? ? Under which circumstances could a BOM be recursive and what the usage...What functions can be executed from here? Material Provision ? ? Describe ...
2015数据结构实验手册_电脑基础知识_IT/计算机_专业资料
特别是多文件大型工程的编 程;了解 ACM 竞赛的赛题,掌握参加 ACM 竞赛的基本...Step 2. Write recursive version functions of inOrder, preOrder and postOrder...
Chapter 3——homework_IT/计算机_专业资料
Chapter 3——homework_IT/计算机_专业资料。1.Write a function to add two ...3.Write a nonrecursive procedure to reverse a single linked list in O(N...
C语言程序设计大赛资料
(最短路径) Recursive Search Techniques (回溯搜索技术) Minimum Spanning Tree ...竞赛类的黑宝书) 《青少年国际和全国信息学(计算机)奥林匹克竞赛指导)――组合...
2_计算机学院_离散数学期末考试_2011年春季_试卷B0
(For this problem, f and g are non-negative functions.) a) g(x) = ...5. Describe a recursive algorithm for computing 32n where n is a ...
更多相关标签:
计算机竞赛 | 计算机知识竞赛题库 | 高中计算机竞赛 | 计算机奥林匹克竞赛 | 大学生计算机竞赛 | 小学生计算机竞赛 | 中学生计算机竞赛 | 超级计算机竞赛 |