Programming Taskbook

Russian

1100 training tasks on programming

©  M. E. Abramyan (Southern Federal University, Shenzhen MSU-BIT University), 1998–2024

Recursion

Recursion: simple algorithms

It should be noted that all tasks of this subsection can be solved by means of simple iterative algorithms without using of recursion; moreover, in some cases using of recursion leads to inefficient algorithms (see Recur4 and Recur6). Nevertheless, tasks of such a kind allow to receive easily an initial experience in developing of recursive algorithms.

Recur1°. Write a recursive real-valued function Fact(N) that returns the value of N-factorial:

N! = 1·2·…·N,

where N (> 0) is an integer parameter. Using this function, output factorials of five given integers.

Recur2. Write a recursive real-valued function Fact2(N) that returns the value of double factorial of N:

N!! = N·(N−2)·(N−4)·…,

where N (> 0) is an integer parameter; the last factor of the product equals 2 if N is an even number, and 1 otherwise. Using this function, output double factorials of five given integers.

Recur3. Write a recursive real-valued function PowerN(X, N) that returns the power X^N (X ≠ 0 is a real number, N is an integer) calculated as follows:

X ⁰ = 1,
X ^N = (X ^{N div 2})² if N is a positive even number,
X ^N = X·X ^N−1 if N is a positive odd number,
X ^N = 1/X ^−N if N < 0,

where "div" denotes the operator of integer division. Using this function, output powers X^N for a given real number X and five given integers N.

Recur4°. Write a recursive integer function Fib1(N) that returns the Fibonacci number F_N (N is a positive integer). The Fibonacci numbers F_K are defined as:

F₁ = F₂ = 1,        F_K = F_K−2 + F_K−1,    K = 3, 4, … .

Using the function Fib1, find the Fibonacci numbers F_N for five given integers N; output the value of each Fibonacci number and also the amount of the recursive function calls, which are required for its calculation.

Recur5°. Write a recursive integer function Fib2(N) that returns the Fibonacci number F_N (N is a positive integer). The Fibonacci numbers F_K are defined as:

F₁ = F₂ = 1,        F_K = F_K−2 + F_K−1,    K = 3, 4, … .

The integer N is assumed to be not greater than 20. Decrease the amount of recursive calls of the function Fib2 (in comparison with the Fib1 function from the task Recur4) by means of using an additional array of integers that should store the Fibonacci numbers having been calculated. Using the Fib2 function, output the Fibonacci numbers F_N for five given integers N.

Recur6. Write a recursive integer function Combin1(N, K) that returns C(N, K) (the number of combinations of N objects taken K at a time) using the following recursive relations (N and K are integers, N > 0, 0 ≤ K ≤ N):

C(N, 0) = C(N, N) = 1,
C(N, K) = C(N − 1, K) + C(N − 1, K − 1)    if 0 < K < N.

Using the function Combin1, find the numbers C(N, K) for a given integer N and five given integers K; output the value of each number and also the amount of the recursive function calls, which are required for its calculation.

Recur7. Write a recursive integer function Combin2(N, K) that returns C(N, K) (the number of combinations of N objects taken K at a time) using the following recursive relations (N and K are integers, N > 0, 0 ≤ K ≤ N):

C(N, 0) = C(N, N) = 1,
C(N, K) = C(N − 1, K) + C(N − 1, K − 1)    if 0 < K < N.

The integer N is assumed to be not greater than 20. Decrease the amount of recursive calls of the function Combin2 (in comparison with the Combin1 function from the task Recur6) by means of using an additional two-dimensional array of integers that should store the numbers C(N, K) having been calculated. Using the Combin2 function, output the numbers C(N, K) for a given integer N and five given integers K.

Recur8. Write a recursive real-valued function RootK(X, K, N) that returns an approximate value of a K-th root of X using the following formulas:

Y₀ = 1,        Y_N+1 = Y_N − (Y_N − X/(Y_N)^K−1)/K,

where X (> 0) is a real number, K (> 1), N (> 0) are integers, Y_N denotes RootK(X, K, N) for a fixed values of X and K. Using this function, output approximate values of a K-th root of X for a given X, K and six integers N.

Recur9. Write a recursive integer function GCD(A, B) that returns the greatest common divisor of two positive integers A and B. Use the Euclidean algorithm:

GCD(A, B) = GCD(B, A mod B),    if B ≠ 0;        GCD(A, 0) = A,

where "mod" denotes the operator of taking the remainder after integer division. Using this function, find the greatest common divisor for each of pairs (A, B), (A, C), (A, D) provided that integers A, B, C, D are given.

Recur10°. Write a recursive integer function DigitSum(K) that returns the sum of digits of an integer K (the loop statements should not be used). Using this function, output the sum of digits for each of five given integers.

Recur11. Write a recursive integer function MaxElem(A, N) that returns the maximal element of an array A of N integers (1 ≤ N ≤ 10; the loop statements should not be used). Using this function, output the maximal elements of three given arrays A, B, C whose sizes are N_A, N_B, N_C respectively.

Recur12. Write a recursive integer function DigitCount(S) that returns the amount of digit characters in a string S (the loop statements should not be used). Using this function, output the amount of digit characters for each of five given strings.

Recur13. Write a recursive logical function Palindrome(S) that returns True if a string S is a palindrome (i. e., it is read equally both from left to right and from right to left), and False otherwise; the loop statements should not be used. Output return values of this function for five given string parameters.

Recursion: parsing of expressions

Input strings are assumed to contain no blank characters in all tasks of this subsection.

The loop statements should not be used for solving these tasks.

Recur14°. Given a string S that represents a correct expression of integer type, output the value of this expression. The expression is defined as follows:

<expression>	::=	<digit> | <expression> + <digit> |
		<expression> − <digit>

Recur15°. Given a string S that represents a correct expression of integer type, output the value of this expression. The expression is defined as follows:

<expression>	::=	<term> | <expression> + <term> |
		<expression> − <term>
<term>	::=	<digit> | <term> * <digit>

Recur16°. Given a string S that represents a correct expression of integer type, output the value of this expression. The expression is defined as follows:

<expression>	::=	<term> | <expression> + <term> |
		<expression> − <term>
<term>	::=	<element> | <term> * <element>
<element>	::=	<digit> | (<expression>)

Recur17°. Given a string S that represents a correct expression of integer type, output the value of this expression. The expression is defined as follows:

<expression>	::=	<digit> |
		(<expression><operator><expression>)
<operator>	::=	+ | − | *

Recur18°. A nonempty string S that represents an expression of integer type is given (see the expression definition in Recur17). Output True if the given expression is a correct one, otherwise output False.

Recur19. A nonempty string S that represents an expression of integer type is given (see the expression definition in Recur17). Output 0 if the given expression is a correct one, otherwise output the order number of its first character that is invalid, superfluous or missing.

Recur20. Given a string S that represents a correct expression of integer type, output the value of this expression. The expression is defined as follows (functions M and m return their maximal and minimal argument respectively):

<expression>	::=	<digit> | M(<expression> , <expression>) |
		m(<expression> , <expression>)

Recur21°. Given a string S that represents a correct expression of logical type, output the value of this expression. The expression is defined as follows ("T" means True, "F" means False):

<expression>	::=	T | F | And(<expression> , <expression>) |
		Or(<expression> , <expression>)

Recur22. Given a string S that represents a correct expression of integer type, output the value of this expression. The expression is defined as follows (functions M and m return their maximal and minimal argument respectively):

<expression>	::=	<digit> | M(<arguments>) | m(<arguments>)
<arguments>	::=	<expression> | <expression> , <arguments>

Recur23. Given a string S that represents a correct expression of logical type, output the value of this expression. The expression is defined as follows ("T" means True, "F" means False):

<expression>	::=	T | F | And(<arguments>) | Or(<arguments>)
<arguments>	::=	<expression> | <expression> , <arguments>

Recur24. Given a string S that represents a correct expression of logical type, output the value of this expression. The expression is defined as follows ("T" means True, "F" means False):

<expression>	::=	T | F | And(<arguments>) |
		Or(<arguments>) | Not(<expression>)
<arguments>	::=	<expression> | <expression> , <arguments>

Recursion: backtracking

Recur25°. A tree of depth N is given. Each internal node of the tree has K (< 10) children that are numbered from 1 (the most left child) to K (the most right child). The number of the tree root is 0. Create a text file (with a given name) whose lines contain paths from the root to all tree leaves. Paths must be ordered from the most left path ("011...1") to the most right path (for instance, "033...3" provided that K = 3); the last nodes of path must be changed faster than the first ones.

Recur26. A tree of depth N is given. Each internal node of the tree has K (< 10) children that are numbered from 1 (the most left child) to K (the most right child). The number of the tree root is 0. Create a text file (with a given name) whose lines contain paths from the root to all tree leaves; each path must satisfy the following additional condition: adjacent nodes of the path have different numbers. The order of paths must be the same as in Recur25.

Recur27°. A tree of depth N is given (N is an even number). Each internal node of the tree has two children; the left child "A" with the weight 1 and the right child "B" with the weight −1. The tree root "C" has the weight 0. Create a text file (with a given name) whose lines contain paths from the root to all tree leaves; each path must satisfy the following additional condition: the total weight of all path nodes is equal to 0. The order of paths must be the same as in Recur25.

Recur28. A tree of depth N is given; see the description of tree nodes in Recur27. Create a text file (with a given name) whose lines contain paths from the root to all tree leaves; each path must satisfy the following additional condition: the total weight of any initial part of the path nodes is nonnegative. The order of paths must be the same as in Recur25.

Recur29. A tree of depth N is given. Each internal node of the tree has three children; the left child "A" with the weight 1, the middle child "B" with the weight 0, the right child "C" with the weight −1. The tree root "D" has the weight 0. Create a text file (with a given name) whose lines contain paths from the root to all tree leaves; each path must satisfy two additional conditions: the total weight of any initial part of the path nodes is nonpositive, and the total weight of all path nodes equals 0. The order of paths must be the same as in Recur25.

Recur30. A tree of depth N is given; see the description of tree nodes in Recur29. Create a text file (with a given name) whose lines contain paths from the root to all tree leaves; each path must satisfy two additional conditions: adjacent nodes of the path have different letters, and the total weight of all path nodes equals 0. The order of paths must be the same as in Recur25.

Designed by
M. E. Abramyan and V. N. Braguilevsky

Last revised:
01.01.2024