简单学习网 让学习变简单
当前位置:首页 >> 学科竞赛 >>

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.


Recursive Functions计算机竞赛

Recursive Functions计算机竞赛_学科竞赛_高中教育_教育专区。2015~2016年度美国计算机竞赛试题包括试题、答案和竞赛辅导 Recursive Functions A definition that defines ...


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


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

ExperimentReport-User difined function

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


recursive 递回 recursively 递回地 recycler 回收站 redefinition 重复定义 ...functions 终止函式 termination handler 终止处理常式 terms of use 使用规定 ...


Introduce_to_Magma_by_Chinese_计算机软件及应用_IT/计算机_专业资料。代数学计算...(7) 递归函数(Recursive functions) Magma 也编写了独立的递归结构。这里只举一...


Freepascal错误代码一览表_IT/计算机_专业资料。信息学第14 周 Freepascal 错误...This error can easily occur if you have recursive functions. 203 Heap ...


义隆单片机_总结_计算机软件及应用_IT/计算机_专业资料。义隆单片机,个人使用过程...?Recursive functions are not supported in the compiler. (不支持递归) ?Do ...

Google C++ Style Guide

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

Code Review Checklist

Code Review Checklist_IT/计算机_专业资料。下面是我们认为的几个小提示可以让...Recursive functions should run with a reasonable amount of stack space. ...

网站首页 | 网站地图
All rights reserved Powered by 简单学习网
copyright ©right 2010-2021。