

'''
----------------------------------------------------------------------------------------
  P R O B L E M S   S E T    [A]
----------------------------------------------------------------------------------------

Determine the output the function call WITHOUT running the program.

Example and analysis
====================

def rec1( n ):
    if n < 1: return 2
    return 1 + rec1( n-1 ) + rec1( n-2 )
# call:
rec1(5)

Each node n the tree diagram represents one function call,
the value in the node is the value of the parameter
                                  ____________________[5]____________________
                      ___________[4]____________                    _______[3]_____
           ________[3]_____             ______[2]___         ______[2]___      __[1]___
    ______[2]____      __[1]__      ___[1]___     [0]     __[1]___     [0]    [0]   [-1]
 __[1]__      [0]     [0]   [-1]   [0]    [-1]           [0]   [-1]
[0]   [-1]

The next tree scheme is based on the previous one,
the return value of the corresponding function call is appended
to each node.
                                  ____________________[5]38__________________
                      ___________[4]23__________                    _______[3]14___
           ________[3]14___             ______[2]8__         ______[2]8__      __[1]5__
    ______[2]8___      __[1]5_      ___[1]5__     [0]2    __[1]5__     [0]2   [0]2  [-1]2
 __[1]5_      [0]2    [0]2  [-1]2  [0]2   [-1]2          [0]2  [-1]2
[0]2  [-1]2

The function call rec1(5) returns value 38.

PROBLEMS
========

-- 1. --
def rec2( n ):
    if n < 1: return 1
    return 2 + rec2( n-1 ) + rec2( n-2 )
# call:
rec1(5)

   rec2(5) = 2 + rec2(4) + rec2(3)   = 2 + 22 + 13 = 37
   rec2(4) = 2 + rec2(3) + rec2(2)   = 2 + 13 +7 = 22
   rec2(3) = 2 + rec2(2) + rec2(1)   = 2 + 7 + 4 = 13
   rec2(2) = 2 + rec2(1) + rec2(0)   = 2 + 4 + 1 = 7
   rec2(1) = 2 + rec2(0) + rec2(-1)  = 2 + 1 + 1 = 4
   rec2(0) = 1
   rec2(-1)= 1



-- 2. --
def rec3( n ):
    if n < 2: return 1
    return 1 + rec3( n-1 ) + rec3( n-2 )
# call:
rec1(5)

-- 3. --
def rec4( n ):
    if n < 2: return 2
    return 1 + rec4( n-2 ) + rec4( n-3 )
# call:
rec1(6)

----------------------------------------------------------------------------------------
  P R O B L E M S   S E T    [B]
----------------------------------------------------------------------------------------

Describe how the return value of the function depends on
 the value(s) of its input parameter.

Example
def rec5( x, y ):
    if x >= y: return x
    return rec5( x+1, y )

The function returns maximum of x and y.
( If x is bigger than or equal to y then it is immediately returned
  as a result.
  If, on the other hand, x is smaller then y then the function
  repeatedly calls itself and increases the value of x until
  it is equal to y, which was originally the bigger of the two.)

Functions to analyze

-- 4. --
def rec6( x, y ):
    if x < y: return rec6(x+1,y)
    return x

-- 5. --
def rec7( x, y ):
    if y > 0: return rec7(x, y-1) + 1
    return x;

-- 6. --
def rec8( x, y ):
    if y > 0: return rec8(x-1, y) - 1
    return y;

----------------------------------------------------------------------------------------
  P R O B L E M S   S E T    [C]
----------------------------------------------------------------------------------------

-- 7. --
Determine exactly the return value of the call f9(100),
provided that the function can run a return the result in some reasonable time.
def f9( N ):
    if N < 1: return 2
    return f9( N-1 ) + f9( N-1 )

-- 8. --
Write a recursive function which will print an isosceles right triangle filled with character '#'.
The number of lines in the triangle will be the parameter of the function.
(Isosceles triangle = the length of both shorter sides is the same )
Example:
f(5)
#
##
###
####
#####
######

-- 9. --
Write a recursive function which will print an right triangle filled with character 'x'.
The number of x's along the longer cathetus (side) will be twice as big as the
 number of of x's along the shorter cathetus (side).
The number of lines in the triangle will be the parameter of the function.
Example
f(5)
##########
  ########
    ######
      ####
        ##


-- 10. --
Write a recursive function which will return the sum of the squares
of the first N positive integers
It holds for f:  f(1) == 1, f(2) = 1+4 = 5, f(3) = 1 + 4 + 9 = 14, f(4) = 30, etc.

-- 11. --
Write a recursive function which will return the sum of all positive integers less than or
equal to N which are not divisible by 3.
It holds for f:  f(1) == 1, f(2) = 1+2 = 3, f(3) = 1 + 2 (3 is not included, it si divisible by 3),
f(4) = 1 + 2 + 4 = 7, f(5) = 1 + 2 + 4 + 5 = 12,
f(6) = 1 + 2 + 4 + 5 = 12  (6 is not included, it si divisible by 3),
f(7) = 1 + 2 + 4 + 5 + 7 = 19, etc.

-- 12. --
Write a recursive function which will return a list of all pairs of the values
in a given list of integers. The list will be the input parameter of the function.
It must hold, for each pair in the output, that the sum of the pair is divisible by 3.
(You may consider implementing a loop in the body of the function.)

[ 6, 5, 4, 3, 2]

[6 5] [6 4] [6 3] [6 2]
      [5 4] [5 3] [5 2]
            [4 3] [4 2]
                  [3 2]

Idea: Produce all pairs of elements in the rest of the array, not including
the first element.



-- 13. --
Write a recursive function which will return a list of all triples of the values
in a given list of integers. The list will be the input parameter of the function.
It must hold, for each triple in the output, that the sum of the triple is positive.

-- 14. --
Write a recursive function which will return a list of tuples of the values
in a given list of integers. The list will be the input parameter of the function.
It must hold, for each tuple in the output, that the sum of the elements in the tuple
is equal to another given value K.
The tuples may be of different lengths.
Example
input: [ 2, 7, 3, 5, 11, 4, 8 ], K = 20
output:
[3, 5, 4, 8]
[7, 5, 8]
[2, 7, 3, 8]
The method you should avoid is to generate all possible tuples and only later
remove those which sum is not equal to K.

-- 15. --
Determine the value of A(4, 4). Function A(m, n) is defined:
def A( m, n ):
    if m == 0: return  n + 1
    if n == 0: return A( m-1, 1 )
    if m > 0 and n > 0: return A( m-1, A(m, n-1) )

'''