# ---------------------------------------------------------------------
#      S U M   O F   D I G I T S
# ---------------------------------------------------------------------

# --------------  EXAMPLE 1  (Global var) -----------------------------


# Compute recursively the sum of al digits in an integer.
'''
Method by Example:
Integer 7136,

total_sum is 0
## level 0: ##
add 6 to total_sum
recurse on 713:
    ## level 1: ##
    add 3 to total_sum
    recurse on 71
        ## level 2: ##
        add 1 to total_sum
        recurse on 7
            ## level 3: ##
            add 7 to total_sum
            recurse on 0
                ## level 4: ##
                processed number is 0, return
                return from level 4
            return from level 3
        return from level 2
    return from level 1
return from level 0
'''

# How do we access the last (0-th order) digit of an integer, say X?
# last digit = X % 10

# How do we remove the last (0-th order) digit of an integer, say X?
# X = X // 10


# Example 1
# The sum is a global variable, outside the recursion process
total_sum = 0
def sumDigits( n ):
    global total_sum
    if n == 0:
        return
    total_sum += n % 10
    sumDigits( n// 10 )

n = 2323111
print("\nExample 1, n =", n)
sumDigits( n )
print( total_sum )

# --------------  EXAMPLE 2  (bottom --> top) -------------------------

# Example 2
# Typical approach:
# The partial result P is computed in deeper levels of recursion,
# the current level adds a small bit B
# and returns the total of P and B.

def sumDigits2( n ):
    if n == 0:
        return 0
    sum = sumDigits2( n//10 )  # partial result P
    sum += n % 10              # small bit B
    return sum

print("\nExample 2, n =", n)
sum = sumDigits2( n )
print( sum )


# Example 2 condensed
# but otherwise identical to Example 2

def sumDigits2b( n ):
    if n == 0:
        return 0
    return n % 10 + sumDigits2b( n//10 )

print("\nExample 2b, n =", n)
sum = sumDigits2( n )
print( sum )

# --------------  EXAMPLE 3  (top --> bottom) -------------------------

# Example 3
# The partial result is computed gradually in the upper (top)
# levels of recursion and it is propagated to deeper levels of recursion.
# At the bottom level of recursion the result is complete.
# This approach differs from the previous one (s) where the result is
# complete only when the recursion returns from all levels.


def sumDigits3( n, sumSoFar ):
    if n == 0:
        return sumSoFar
    sumSoFar += n % 10
    n = n // 10
    return sumDigits3( n, sumSoFar )

print("\nExample 3, n =", n)
sum = sumDigits3( n, 0 )
print( sum )

# Example 3 condensed
# but otherwise identical to Example 3

def sumDigits3b( n, sumSoFar ):
    if n == 0:
        return sumSoFar
    return sumDigits3b( n // 10 , sumSoFar + (n % 10) )

print("\nExample 3b, n =", n)
sum = sumDigits3b( n, 0 )
print( sum )


exit()


'''
Interesting error

def sumDigits2( n, sum ):
    if n == 0:
        return sum
    sum += n % 10
    n = n // 10
    sum += sumDigits2( n, sum )
    return sum

'''



# ---------------------------------------------------------------------
#    M I N
# ---------------------------------------------------------------------

# no recursion
def myMin0( arr ):
    min = arr[0]
    for i in range( 1, len(arr) ):
        if arr[i] < min: min = arr[i]
    return min


# recursion - one call
def myMin1( arr, iFrom ):
    # stop recursion? just a single element?
    if iFrom == len(arr) - 1: return arr[iFrom]

    # more elements
    rightMin = myMin1( arr, iFrom+1 )
    if arr[iFrom] < rightMin: return arr[iFrom]
    else:                     return rightMin


# recursion - two calls
def myMin2( arr, iFrom, iTo ):
     # stop recursion? just a single element?
    if iFrom == iTo: return arr[iFrom]

    # more elements
    iMid = (iFrom + iTo) // 2  # index of middle element
    # recursive calls
    leftMin  = myMin2( arr, iFrom, iMid )
    rightMin = myMin2( arr, iMid+1, iTo )
    # compute return value
    if   leftMin < rightMin: return leftMin
    else:                    return rightMin

# ---------------------------------------------------------------------
#    O D D
# ---------------------------------------------------------------------

# no recursion
def noOfOdd0( arr ):
    noOfOdd = 0
    for i in range( 0, len(arr) ):
        if arr[i] % 2 == 1: noOfOdd += 1
    return noOfOdd

# no recursion
def noOfOdd0a( arr ):
    noOfOdd = 0
    for i in range( 0, len(arr) ): noOfOdd += (arr[i] % 2)
    return noOfOdd


# recursion - one call
def noOfOdd1( arr, iFrom ):
    # stop recursion? just a single element?
    if iFrom == len(arr): return 0

    # more elements
    rightNoOfOdd = noOfOdd1( arr, iFrom + 1  )
    if arr[iFrom] % 2 == 1: return 1 + rightNoOfOdd
    else:                   return 0 + rightNoOfOdd

# recursion - one call
def noOfOdd1a( arr, iFrom ):
    if iFrom == len(arr): return 0
    return arr[iFrom] % 2 + noOfOdd1a( arr, iFrom + 1 )


# recursion - two calls
def noOfOdd2( arr, iFrom, iTo ):
     # stop recursion? just a single element?
    if iFrom == iTo:
         if arr[iFrom] % 2 == 1: return 1
         else:                   return 0

    # more elements
    iMid = (iFrom + iTo) // 2  # index of middle element
    # recursive calls
    leftNoOfOdd  = noOfOdd2( arr, iFrom, iMid )
    rightNoOfOdd = noOfOdd2( arr, iMid+1, iTo )
    # compute return value
    return leftNoOfOdd + rightNoOfOdd

# recursion - two calls
def noOfOdd2a( arr, iFrom, iTo ):
    if iFrom == iTo: return arr[iFrom] % 2
    iMid = (iFrom + iTo) // 2
    return noOfOdd2a( arr, iFrom, iMid ) + noOfOdd2a( arr, iMid+1, iTo )


# recursion - five calls
def noOfOdd5a( arr, iFrom, iTo ):
    if iFrom > iTo: return 0 # be careful
    if iFrom == iTo: return arr[iFrom] % 2

    iFifth1 = iFrom + 1*(iTo-iFrom) // 5
    iFifth2 = iFrom + 2*(iTo-iFrom) // 5
    iFifth3 = iFrom + 3*(iTo-iFrom) // 5
    iFifth4 = iFrom + 4*(iTo-iFrom) // 5

    return   noOfOdd5a( arr, iFrom, iFifth1 ) \
           + noOfOdd5a( arr, iFifth1+1, iFifth2 ) \
           + noOfOdd5a( arr, iFifth2+1, iFifth3 ) \
           + noOfOdd5a( arr, iFifth3+1, iFifth4 ) \
           + noOfOdd5a( arr, iFifth4+1, iTo )

# ---------------------------------------------------------------------
#    M A I N
# ---------------------------------------------------------------------

arr = [8, 13, 7, 15, 4, 6, 10, 5, 22, 11,]

print( arr )
print()
print( myMin0( arr ))
print( myMin1( arr, 0 ))
print( myMin2( arr, 0, len(arr)-1 ))
print()

print( noOfOdd0 ( arr ))
print( noOfOdd0a( arr ))
print( noOfOdd1 ( arr, 0 ))
print( noOfOdd1a( arr, 0 ))
print( noOfOdd2 ( arr, 0, len(arr)-1 ))
print( noOfOdd2a( arr, 0, len(arr)-1 ))
print( noOfOdd5a( arr, 0, len(arr)-1 ))