def factorial(n):
    '''
    n: integer (n>=1)
    returns n! (1*2*3*..*n)
    '''
    
    if n==1:
        return 1
    else:
        return n * factorial(n-1)  # n * (n-1)!
    
print('4!=', factorial(4))
print('10!=', factorial(10))

def fibonacchi(n):
    '''
    n: integer
    return Fibonacchi number of n
    '''
    
    if n < 2:
        return 1
    else:
        return fibonacchi(n-1) + fibonacchi(n-2)
    
for i in range(10):
    print('Fibonnachi(', i, ')=' ,fibonacchi(i), sep='')

"""
Explanation: Recursion (Recursive Program)
Recursion is a very important way of thinking in programming. It is a function that calls itself. Typical examples are Factorial and Fibonacchi Function.
5 out of 12 problems in ICPC 2016 Yangon regional were related to Recusion.
End of explanation
"""


def factorial_s(n):
    '''
    n: integer
    returns n! (1*2*3*..*n)
    '''
    
    ret = 1
    for i in range(1, n+1): # from 1 to n
        ret *= i
    
    return ret

print('4!=', factorial_s(4))
print('10!=', factorial_s(10))

def fib2(n):
    '''
    n: integer
    return Fibonacchi number of n
    '''
    
    if n < 2:
        return 1
    
    n2 = n1 = 1
    for i in range(2, n+1):
        ret = n1 + n2
        n2 = n1
        n1 = ret
    return ret
    
for i in range(10):
    print('Fibonnachi_simple(', i, ')=' ,fib2(i), sep='')

"""
Explanation: Any question ???

Why so complex ???
Is it really necessary ???
They can be easier and faster !!!
End of explanation
"""


from IPython.display import Image, display_png

display_png(Image("Merge-Sort-Tutorial.png"))

import sys

def merge(list1, list2):
    print('Merge:', list1, list2, end= '->', file=sys.stderr)
    merged_list = list()  # Create empty list
    
    while (list1 and list2):  # While there are elements in both list
        if list2[0] < list1[0]:
            merged_list.append(list2.pop(0))
        else:
            merged_list.append(list1.pop(0))
            
    if list1: merged_list.extend(list1)  # append if list1 is not empty
    if list2: merged_list.extend(list2)
    
    print(merged_list, file=sys.stderr)
    return merged_list

def mergeSort(list_x):
    print('Merge Sort:', list_x, file=sys.stderr)
    if len(list_x) > 1:
        mid_index = len(list_x) // 2
        list1 = mergeSort(list_x[:mid_index])  # not include mid_index
        list2 = mergeSort(list_x[mid_index:])  # include mid_index
        list_x = merge(list1, list2)
    return list_x

import random

num_elem = random.randrange(10) + 10

r_list = [random.randrange(100) for i in range(num_elem)]
#r_list = list()
#for i in range(num_elem):
#    r_list.append(random.randrange(100))
    
print('Initial List:', r_list)
print('Sorted List:', mergeSort(r_list))

"""
Explanation: So why recursion is important ?

Sometime it is difficult to calculate from start point
Recursion sometimes shows drastic effect

Example: Merge Sort  https://www.geeksforgeeks.org/merge-sort/
End of explanation
"""


def f(n):
    '''
    n: integer
    return sum of each digit
    '''
    
    digits = list(str(n))
    return (sum(map(int, digits)))

import sys
def g(n):
    print('g()', n, file=sys.stderr, end = ': ')
    while n>10:
        n = f(n)
        print(n, file=sys.stderr, end = ' ')
    print(file=sys.stderr)
    return n

import random

for i in range(5):
    n = random.randrange(1000, 2000000000)
    print(n, g(n))
    
print(1234567892, g(1234567892))

"""
Explanation: Java sample code of Merge Sort
```
import java.util.Scanner;
//import java.util.Arrays ;
// import java.InputMismatchException;
// alds_5b, Aizu Online Judge accept only class name: Main
class Main {
public static long merge_count = 0 ;

static void Merge(int [] A, int low, int mid, int high) {
    int l_size = mid-low ;
    int h_size = high-mid ;
    int []L = new int[l_size] ;
    int []H = new int[h_size] ;

    //System.out.printf("Merge: %d %d %d\n", low, mid, high) ;
    for (int i=0; i&lt;l_size; i++) {
        L[i] = A[low+i] ;
    }
    for (int i=0; i&lt;h_size; i++) {
        H[i] = A[mid+i] ;
    }

    int a_pos=low, l_pos=0, h_pos=0 ;

    while (l_size != 0 &amp;&amp; h_size != 0) {
        if (L[l_pos] &lt;= H[h_pos]) {
            A[a_pos] = L[l_pos] ;
            l_size -= 1 ;
            l_pos += 1 ;
        }
        else {
            A[a_pos] = H[h_pos] ;
            h_size -= 1 ;
            h_pos += 1 ;
        }
        a_pos += 1 ;
        merge_count++ ;
    }

    while (l_size != 0) {
        A[a_pos] = L[l_pos] ;
        l_size -= 1 ;
        l_pos += 1 ;
        a_pos += 1 ;
        merge_count++ ;
    }

    while (h_size != 0) {
        A[a_pos] = H[h_pos] ;
        h_size -= 1 ;
        h_pos += 1 ;
        a_pos += 1 ;
        merge_count++ ;
    }

}

static void Merge_sort(int [] A, int low, int high) {
    //System.out.printf("Merge_sort: %d %d\n", low, high) ;
    if (low + 1 &lt; high) {   // if 2 or more elements in the List
        int mid = (low + high) / 2 ;
        Merge_sort(A, low, mid) ;
        Merge_sort(A, mid, high) ;
        Merge(A, low, mid, high) ;
    }
}

public static void main(String args[]) {
    Scanner scanner = new Scanner(System.in) ;
    String s = scanner.nextLine() ;

    int elem_count ;
    elem_count = Integer.parseInt(s) ;
    int A[] = new int[elem_count] ;

    for (int i=0; i&lt;elem_count; i++) {
        A[i] = scanner.nextInt() ;
    }

    scanner.close() ;
    Merge_sort(A, 0, elem_count) ;

    for (int i=0; i&lt;elem_count; i++) {
        String end_mark = " " ;
        if (i==elem_count-1) end_mark = "\n" ;
        System.out.print(A[i] + end_mark) ;
    }
    System.out.println(merge_count) ;
}

}
```
Caution!

Take care of end-less loop (think exit condition at first)
Take care of stack overflow
Consider
if it's possible to calculate from start
performance improvement whether intermediate result can be reused



UVa 11332
https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2307
Problem Description
For a positive integer n, let f(n) denote the
sum of the digits of n when represented in base 10.
It is easy to see that the sequence of numbers
n, f(n), f(f(n)), f(f(f(n))), . . . eventually
becomes a single digit number that repeats forever.
Let this single digit be denoted g(n).
For example, consider n = 1234567892.
Then:
f(n) = 1+2+3+4+5+6+7+8+9+2 = 47
f(f(n)) = 4 + 7 = 11
f(f(f(n))) = 1 + 1 = 2
Therefore, g(1234567892) = 2.
Input
Each line of input contains a single positive integer
n at most 2,000,000,000. Input is terminated
by n = 0 which should not be processed.
Output
For each such integer, you are to output a single
line containing g(n).
Sample Input
2
11
47
1234567892
0
Sample Output
2
2
2
2
End of explanation
"""


