C# For Dummies
Chapter 10. Recursion
1. Write a program to simulate n
nested loops from 1 to n.
Guidelines: Create a recursive method Loops(int k), perform a forloop from 1 to n and make a recursive call Loops(k1) in the loop. The bottom of the recursion is when k < 0. Initially invoke Loops(n1).
Solution:
Link
2. Write a program to generate
all variations with duplicates of
n
elements class
k
.
Example input:
n = 3, k = 2
Example output:
Think about and implement an
iterative algorithm as well.
Guidelines: The
recursive solution is to modify the algorithm for
generating N nested loops. In fact you need
k nested loops from 1 to n.
The
iterative solution is as follows: start from the
first variation in the lexicographical order:
{1, 1, …, 1} k times. To
obtain the next variation, increase the last number. If it becomes greater than
n, change it to 1 and increase the next number on the left. Do the same on the left until the first number goes greater than
n.
Solution:
Link
3. Write a program to generate and print
all combinations with duplicates of
k
elements from a set with
n
elements.
Example input: br />
n = 3, k = 2
Example output:
Think about and implement an
iterative algorithm as well.
Guidelines: Modify the algorithms from
the previous problem and always keep each number equal or greater than the number on the left of it. The easiest way to achieve this is to
generate k nested loops from 1 to n and print only these combinations in which each number is greater or equal than the number on its left. You may optimize this approach to get generate directly an increasing sequence for better performance.
Solution:
Link
4. You are given a
set of strings. Write a
recursive program, which
generates all subsets, consisting exactly
k
strings chosen among the elements of this set.
Example input:
Example output:
Guidelines: Let the strings’ count be
n
. Use the implementation of
k nested loops (recursive or iterative) with additional limitation that
each number is greater than the previous one. Thus you will generate all different subsets of
k
elements in the range
[0…n1]
. For each set consider the numbers from it as indices in the array of strings and print for each number the corresponding string. For the example above, the set
{0, 2}
corresponds to the strings at position 0 and position 2, i.e.
(test, fun)
.
The
iterative algorithm is similar to the iterative algorithm for generating
n nested loops, but is more complicated because it needs to guarantee that each number is greater than the number on its left.
Solution:
Link
5. Write a
recursive program, which prints
all subsets of a given set of N words.
Example input:
Example output:
Think about and implement an
iterative algorithm as well.
Guidelines: You can
use the previous task and
call it N times in order to generate consequently the empty set
(k=0)
, followed by the all subsets with one element
(k=1)
, all subsets with 2 elements
(k=2)
, all subsets with 3 elements
(k=3)
, etc.
The problem has another
very smart iterative solution: run a
loop from 0 to 2N1 and convert each of these numbers to
binary numeral system. For example, for
N=3
you will have the following binary representations of the numbers between 0 to
2N1: 000, 001, 010, 011, 100, 101, 110, 111
Now for each binary representation take those words from the subset for which
have bit 1 on the corresponding position in the binary representation. For instance, for the binary representation \"101\" take the first and the last string (at these positions there is 1) and omit the second string (at this position there is 0). Smart, isn’t it?
Solution:
Link
6. Implement the
mergesort algorithm recursively. In it the initial array is divided into two equal in size parts, which are sorted (recursively via mergesort) and after that the two sorted parts are merged in order to get the whole sorted array.
Guidelines: In case you have any difficulties
search in Internet for \"merge sort\". You are going to find hundreds of implementations, including in C#. The challenge is to avoid allocating a new array for the result at each recursive call, because this is inefficient, and to
use only three arrays in the whole program: two arrays to be merged merge and a third for the result from the merging. You will have to implement merging of two ranges of an array into a range of another array.
Solution:
Link
7. Write a recursive program, which generates and prints
all permutations of the numbers 1, 2, …, n
, for a given integer
n
.
Example input:
n = 3
Example output:
Guidelines:
Recursive algorithm: suppose that the method
Perm(k)
permutes in all possible ways the elements of the array
p[]
at positions from 0 to
k1
(inclusive). Firstly, initialize the array p with the numbers from 1 to N.
Implement recursively Perm(k)
in the following way:
1. If
k==0
, print the current permutation and exit the recursion (bottom of the recursion).
2. Call
Perm(k1)
.
3. For each position
i
from 0 to
k1
do the following:
a. Swap
p[i]
with
p[k]
.
b. Recursively call
Perm(k1)
.
c. Swap back
p[i]
with
p[k]
.
In the beginning call
Perm(k1)
to start the recursive generation.
Iterative algorithm: Read in Wikipedia how to generate from given permutation the next permutation in the lexicographic order iteratively:
en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order.
Solution:
Link
8. You are given an array of integers and a number
N
. Write a recursive program that finds
all subsets of numbers in the array, which have a
sum N
. For example, if we have the array
{2, 3, 1, 1}
and
N=4
, we can obtain
N=4
as a sum in the following two ways:
4=2+31; 4=3+1
.
Guidelines: The problem is not very different from the task with
finding all subsets among a given list of strings. Shall it work fast enough with 500 numbers? Pay attention that we have to print
all subsets with sum N which can be really big amount if
N
is very big and proper numbers exist in the array. For this reason
the task has no efficient solution
Solution:
Link
9. . You are given an array of
positive integers. Write a program that checks whether there is one or more numbers in the array
(subset), whose sum is equal to S. Can you solve the task
efficiently for large arrays?
Guidelines: If we approach the problem by the method of generating of all possibilities, the solution
will not work for more than 2030 numbers. That’s why we may approach it in a very different way in case the elements of the array are only positive, or are
limited in a certain range (for example
[50…50]
). Then we could use the following optimized algorithm based on
dynamic programming:
Assume we are given an array of numbers
p[]
. Let’s denote by
possible(k, sum)
whether we could obtain
sum
by using only the numbers first
k numbers (
p[0], p[1], …, p[k]
). Then, the following
recurrent dependencies are valid:

possible(0, sum) = true
if
p[0] == sum

possible(k, sum) = true
if
possible[k1, sum] == true
or
possible[k1, sump[k]] == true
The formula above shows that we can obtain
sum
from the elements of the array at positions 0 to
k
if one of the following two statements remains:
 The element
p[k]
does not participate in the sum and the sum is obtained from the rest of the elements (from 0 to
k1
);
 The element
p[k]
participates in
sum
and the remainder
sump[k]
is obtained from the rest of the elements (from 0 to
k1
).
The implementation is not complex. Just calculate the recursive formulas by
recursive method. We should be careful and not let already calculated values from the twodimensional array
possible[,]
to be calculated twice. For this purpose we should keep for each possible k and sum the value
possible[k,sum]
. Otherwise the algorithm will not work for more than 2030 elements.
The regeneration of the numbers, which compose the found sum, may be implemented if we
go backwards from the sum n, obtained from the first
k
numbers. At each step we examine how this sum can be obtained from the first
k–1
numbers (by taking the
kth
number or omitting it).
Bear in mind that in the general case all possible sums of the numbers from the input array may be an awful lot. For instance, possible sums of 50
int
numbers in the range
[Int32.MinValue …Int32.MaxValue]
are enough so that we could not sum them in whatever data structure. If, however, all numbers in the input array are positive (as in our case), we could keep the sums in the range
[1…S]
because from the rest we could not obtain sum
S
by adding one or more numbers from the input array.
If the numbers in the input array are not mandatory positive, but are
limited in a range, then all possible sums are limited in some range too and we could use the algorithm described above. For example, if the range of numbers is from 50 to 50, then the least sum is 50*S and the greatest is 50*S.
If the numbers in the input array are random and not limited in a range, then
the problem has no efficient solution.
You could read more about this classical optimization problem in computer science called “
Subset Sum Problem” in the following article in Wikipedia:
http://en.wikipedia.org/wiki/Subset_sum_problem .
Solution:
Link
10. You are given a
matrix with passable and impassable cells. Write a recursive program that finds
all paths between two cells in the matrix.
Guidelines: Note that you need to find all possible paths (not just one of them) so don’t expect your program to run fast for large input data.
Solution:
Link
← Back