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


推荐相关:

计算机全英班09期末

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


acm竞赛的题型分析

(最短路径) Recursive Search Techniques (回溯搜索技术) Minimum Spanning Tree ...(LCS) 1080 human gene functions,1159 palindrome,1458 common subsequence,2192...


计算机专业词汇

recursive 无穷递回 无限递归 information 资讯 信息 infrastructure 公共基础建设 ...(从 viable functions 中挑出的最佳吻合者) binary search 二分搜寻法 二分...


数据结构2013春季A卷

第 2 学期 开课学院: 计算机学院 课程号: ...10. The primary ADT access functions used to ...3. (8p)Write a recursive function named small...


SSD5单选

Which of the following print functions for Thing is the safest and most ...Consider the following definition of a recursive function f. bool f( int ...


2010计算机网络原理B卷答案及评分标准 北交大

2. Please describe how a link-layer switch operates its functions of self...Please explain the resolution process by using recursive query(6) 当主机发出...


重庆大学2013年度算法考题

计算机学院 课程号: 考试日期: 2013.12.26 考试时...Write the recursive formula(递推方程式) to ...and g(n)be asymptotically nonnegative functions. ...


计算机程序编程中的常用英语

(从 viable functions 中挑出的最佳吻合者) binary search 二分搜寻法 二分...recursive 无穷递回 无限递归 information 资讯 信息 infrastructure 公共基础建设 ...


DB2递归查询

db2 -tvf connect_by_functions.sql db2 -tvf connect_by_sample.sql 回页首...NAME ---SQL0347W The recursive common table expression "SRIELAU.N" may ...


pp顾问考题

? ? Under which circumstances could a BOM be recursive and what the usage...What functions can be executed from here? Material Provision ? ? Describe ...

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