recursion関連

is_prime_recursion.py

def is_prime_recursion(n, i=2):

    # base case
    ## easiest case
    if n == 0 or n == 1:
        return False
    ## 終了条件
    ### iをインクリメントしていって最後まで割り切れなかったらprimeなのでTrueを返して終了
    if n == i:
        return True
    ## 中断条件
    ### iで割れたらそこでprimeでないのでFalseを返すして中断
    if n % i == 0:
        return False
      
    # recursive case
    ## index i(>=2)でnが割れなかったら、index iをインクリメントして次の関数を呼ぶ
    if n % i != 0:
        return is_prime_recursion(n, i+1)


for i in range(11):
    print(f"{i} is prime number?", is_prime_recursion(i))

# 0 is prime number? False
# 1 is prime number? False
# 2 is prime number? True
# 3 is prime number? True
# 4 is prime number? False
# 5 is prime number? True
# 6 is prime number? False
# 7 is prime number? True
# 8 is prime number? False
# 9 is prime number? False
# 10 is prime number? False

linear_search_recursion.py

alist = ["Apple", "Banana", "Kiwi", "Peach",
         "Watermelon", "Mango", "Pears",
         "Grapes", "Mangosteen", "Strawberry"]

# targetを見つけたらTrue, 見つからなかったら-1を返す実装
def linear_search_recursion(alist, target):

    current_index = len(alist)

    if len(alist) == 0:
        return -1
    if alist[0] == target:
        return True
    return linear_search_recursion(alist[1:], target)

# found
print(linear_search_recursion(alist, "Apple"))
print(linear_search_recursion(alist, "Mango"))
print(linear_search_recursion(alist, "Strawberry"))

# not found
print(linear_search_recursion(alist, "Mang"))
print(linear_search_recursion(alist, ""))


# targetを見つけたらtargetのindex, 見つからなかったら-1を返す実装
def linear_search_recursion2(alist, target, currnt_index=0):

    # print(f"passed list: {alist}")

    # base case
    if len(alist) == 0:
        return -1
    if alist[0] == target:
        return currnt_index

    # recursive case
    currnt_index += 1
    return linear_search_recursion2(alist[1:], target, currnt_index)

# found
print(linear_search_recursion2(alist, "Apple"))
print(linear_search_recursion2(alist, "Mango"))
print(linear_search_recursion2(alist, "Strawberry"))

# not found
print(linear_search_recursion2(alist, "Mang"))
print(linear_search_recursion2(alist, ""))

recursion_binarysearch.py

alist = ["Australia", "Brazil", "Canada", "Denmark", "Ecuador",
         "France", "Germany", "Honduras", "Iran", "Japan",
         "Korea", "Latvia", "Mexico", "Netherlands", "Oman",
         "Philippines", "Qatar", "Russia", "Spain", "Turkey",
         "Uruguay", "Vietnam", "Wales", "Xochimilco", "Yemen", "Zambia"]


# targetを見つけたらTrue, 見つからなかったら-1を返す実装
def recursion_binarysearch(alist, target):

    # mid_index = (0 + len(alist) - 1) // 2
    mid_index = (len(alist) - 1) // 2

    print(alist)

    # base case
    if len(alist) == 0:
        return -1
    if alist[mid_index] == target:
        return True

    # recursive case
    if alist[mid_index] != target:
        if alist[mid_index] > target:
            return recursion_binarysearch(alist[:mid_index], target)
        elif alist[mid_index] < target:
            return recursion_binarysearch(alist[mid_index+1:], target)


# found
# print(recursion_binarysearch(alist, "Australia"))
# print(recursion_binarysearch(alist, "Honduras"))
# print(recursion_binarysearch(alist, "Philippines"))
# print(recursion_binarysearch(alist, "Zambia"))


# not found
# print(recursion_binarysearch(alist, "Austr"))
# print(recursion_binarysearch(alist, ""))

# targetを見つけたらtargetのindex, 見つからなかったら-1を返す実装
# binaly searchの場合は、indexを返したい場合はlistをsliceして行くのは難しそう
# 引数で素直にindex情報を渡して実装する。再帰はloopを使わず関数を呼ぶことで実装できればひとまず再帰で実装したと言っていいはず
def recursion_binarysearch2(alist, low, high ,target):

    mid = (low + high) // 2
    # base case
    if low > high:
        return -1
    if alist[mid] == target:
        return mid

    # recursive case
    if alist[mid] > target:
        high = mid-1
        return recursion_binarysearch2(alist, low, high, target)
    else: # alit[mid] == targe is impossible in this position.
        low = mid+1
        return recursion_binarysearch2(alist, low, high, target)


# found
print(recursion_binarysearch2(alist, 0 ,len(alist)-1, "Australia"))
print(recursion_binarysearch2(alist, 0 ,len(alist)-1,  "Honduras"))
print(recursion_binarysearch2(alist, 0 ,len(alist)-1,  "Philippines"))
print(recursion_binarysearch2(alist, 0 ,len(alist)-1,  "Zambia"))


# not found
print(recursion_binarysearch2(alist, 0 ,len(alist)-1,  "Austr"))
print(recursion_binarysearch2(alist, 0 ,len(alist)-1,  ""))

recursion_exercise.py

""" Recursion in-class Exercise (7 Problems) """


def bunny_ears(n):
    """
    We have a number of bunnies and each bunny has two big floppy ears.
    We want to compute the total number of ears across all the bunnies recursively
    (without loops or multiplication).

    bunny_ears(0) -> 0
    bunny_ears(1) -> 2
    bunny_ears(2) -> 4
    bunny_ears(3) -> 6
    bunny_ears(50) -> 100
    """
    # base caes
    if n == 0:
        return 0
    if n == 1:
        return 2 * n
    else: # recursive case
        return 2 + bunny_ears(n-1)

# print(bunny_ears(3))


def count_x(string):
    """
    Given a string, compute recursively (no loops) the number of lowercase 'x' chars in the string.

    count_x("xxhixx") -> 4
    count_x("xhixhix") -> 3
    count_x("hi") -> 0
    count_x("x") -> 1
    count_x("") -> 0
    count_x("hihi") -> 0
    """

    cnt = 0

    # base case
    if len(string) == 0:
        return 0
    if len(string) == 1:
        if string == "x":
            return 1

    # recursive case
    if string[0] == 'x':
        return 1 + count_x(string[1:])
    else:
        return count_x(string[1:])

# print(count_x("xhixhix"))

def no_x(string):
    """
    Given a string, compute recursively a new string where all the 'x' chars have been removed.

    no_x("xaxb") -> "ab"
    no_x("abc") -> "abc"
    no_x("xx") -> ""
    no_x("axxbxx") -> "ab"
    no_x("Hellox") -> "Hello"
    """

    # core case
    if len(string) == 0:
        return ""
    # if len(string) == 1:
    #     if string == "x":
    #         return ""
    #     else:
    #         return string

    # recursive case
    if string[0] == "x":
        return no_x(string[1:])
    else:
        return string[0] + no_x(string[1:])

# print(no_x("xaxb"))
# print(no_x("abc"))
# print(no_x("xx"))
# print(no_x("axxbxx"))
# print(no_x("Hellox"))


def array_6(nums, index):
    """
    Given an array of ints, compute recursively if the array contains a 6.
    We'll use the convention of considering only the part of the array that begins at the given index.
    In this way, a recursive call can pass index+1 to move down the array.
    The initial call will pass in index as 0.

    array_6([1, 6, 4], 0) -> True
    array_6([1, 4], 0) -> False
    array_6([6], 0) -> True
    array_6([], 0) -> True
    array_6([1, 9, 4, 6, 6], 0) -> True
    """

    # core case
    if len(nums) == 0:
        return False
    if nums[0] == 6:
        return True
    else: # recursive case
        return array_6(nums[1:], index+1)

print(array_6([1, 6, 4], 0))
print(array_6([1, 4], 0))
print(array_6([6], 0))
print(array_6([], 0))
print(array_6([1, 9, 4, 6, 6], 0))

def all_star(string):
    """
    Given a string, compute recursively a new string where all the adjacent chars are now separated by a "*".

    all_star("hello") -> "h*e*l*l*o"
    all_star("abc") -> "a*b*c"
    all_star("ab") -> "a*b"
    all_star("3.14") -> "3*.*1*4"
    all_star("a") -> "a"
    all_star("") -> ""
    """

    # core case
    if len(string) == 0:
        return ""
    if len(string) == 1:
        return string

    return string[0] + "*" + all_star(string[1:])

print(all_star("hello"))
print(all_star("abc"))
print(all_star("ab"))
print(all_star("3.14"))
print(all_star("a"))
print(all_star(""))

recursion_how_to_work.py

"""
https://www.geeksforgeeks.org/recursion/
recursionの動きを把握するためだけのコード
stackに入っていく順番と実行されていく順番を確認
"""


def printFun(test):

    # base case
    if test < 1:
        print("-----------------")
        return
    # recursive case
    else:
        print(f"called printFun({test})")
        printFun(test-1)
        print(f"returned printFun({test})")
        return

printFun(5)

# called printFun(5)
# called printFun(4)
# called printFun(3)
# called printFun(2)
# called printFun(1)
# --------------
# returned printFun(1)
# returned printFun(2)
# returned printFun(3)
# returned printFun(4)
# returned printFun(5)

sum_recursion.py

"""
calculate 0+(1+2+,,,,,,+x)
"""

# iterative
def fun2(x):
    sum = 0
    for i in range(1,x+1):
        sum += i
    return sum

print("fun2(x)",fun2(5))
#---> fun2(x) 15

# recursive
def fun2_recursion(x):
    # base case
    # 0が初期値
    if x == 0:
        return 0
    else:
        return x + fun2_recursion(x-1)

print("fun2_recursion(x)", fun2_recursion(5))
#---> fun2_recursion(x) 15


"""
calculate (1+2+3+,,,,,+x) + y = (1+x)*x/2 +y
with fixed value y
"""

# iterative
def fun1(x, y):
    sum = y
    for i in range(1,x+1):
        sum += i
    return sum

print(fun1(5,2))

# recursive case1
# geeksofgeeks
# Practice Questions for Recursion | Set 1
# Question 1
# 仕組みはわかったけど、自分でこれを実装できる気がしない。↑の方が現実的かなと思う。
# https://www.geeksforgeeks.org/practice-questions-for-recursion/
def fun1_recursion(x, y):
    # base case
    if x ==0:
        return y
    else:
        return fun1(x-1, x+y)

# recursive case2
# 単純に初期値がyだと考えた実装、これは理解しやすい
def fun11_recursion(x, y):
    if x == 0:
        return y
    else:
        return x + fun11_recursion(x-1, y)

print("fun11_recursion(x, y)", fun11_recursion(5, 2))