Problem I. 259. (February 2011)
I. 259. Recursion is a tool often used both in mathematics and in informatics. It can appear in different stages during the solution of a problem, for example, in the specification part, in algorithmic planning, or during the coding in the programming language.
One typically uses a function to give the specification. This function effectively establishes a connection between the input and the output. Let us first consider the power function for example. A possible definition is the following: \(\displaystyle x^{n}=x\cdot x^{n1}\) and \(\displaystyle x^{0}=1\), or, in other words,
\(\displaystyle
\mathop{\rm power}\, (x,n)=
\begin{cases}
1 & \text{if \ } n=0, \\
x \cdot \mathop{\rm power}\, (x,n1) & \text{if \ } n>0.
\end{cases}
\)
In this way, the computation of \(\displaystyle 5^{3}\) is reduced to \(\displaystyle 5\cdot 5^{2}\), that is to \(\displaystyle 5^{2}\), then to \(\displaystyle 5^{1}\), finally, to \(\displaystyle 5^{0}\), which is defined separately. The above task can be solved effectively with a recursive algorithm:
In functional programming languages, like ImagineLogo, coding simply follows from the above:
Nonrecursive languages, like Pascal, may also allow this coding to be implemented:
Algorithms and programs defined iteratively can be rewritten in a recursive fashion. Sequences and conditionals, as the most important algorithmic blocks, can be transformed without any difficulty or modification. Loops however require some revision to make them recursive. The following scheme illustrates how to reformulate a pretest loop (that is, a loop in which the loop test is evaluated before the body of the loop):
Example. Create the sequence of natural numbers between \(\displaystyle A\) and \(\displaystyle B\) (\(\displaystyle 1\le
A,B\le 100\)). In the solution below, the procedure Előállít(5, 10, Sor, 1) puts the sequence 5 6 7 8 9 10 into the array Sor.
I. Iterative solution:
II. Recursive solution:
Your task is to create a program that produces the following sequences without using any loop.
\(\displaystyle a)\) Write a function to create a ``mountain of numbers'' of height \(\displaystyle N\) (\(\displaystyle N\ge 1\)). Example: mountain 5 Result: 1 2 3 4 5 4 3 2 1;
\(\displaystyle b)\) Write a function to create a ``mountain chain of numbers'' of height \(\displaystyle N\). Example: chain 4 Result: 1 1 2 1 1 2 3 2 1 1 2 3 4 3 2 1;
\(\displaystyle c)\) Write a function to create a ``staircase of numbers'' of height \(\displaystyle N\). Example: staircase 6 Result: 1 2 2 3 3 3 4 4 4 4 5 5 5 5 5 6 6 6 6 6 6;
\(\displaystyle d)\) Write the first \(\displaystyle N\) elements of the following recursive sequence: \(\displaystyle a_{1}=1\) and \(\displaystyle a_{n}=4  3a_{n1}\).
The first argument to your program is the value of \(\displaystyle N\), while the output file is specified by the second argument. The output file should contain one sequence in each line. Elements of a sequence should be separated by a space. You should not use loops when writing into the file.
The source code (i259.pas, i259.cpp, ...) together with a short documentation (i259.txt, i259.pdf, ...)  also describing which developer environment to use for compiling, further a brief description of your solution  should be submitted.
(10 pont)
Deadline expired on 10 March 2011.
Sorry, the solution is available only in Hungarian. Google translation
Mintamegoldásként Szabó Attila (Pécs, Leőwey Klára Gimnázium, 10. osztály) tanuló munkáját közöljük: i259.pas
Statistics:
