再帰関数と匿名関数


1.再帰関数
関数の内部で、他の関数を呼び出すことができます.関数が内部で自身を呼び出す場合、この関数は再帰関数です.
def calc(n):
    print(n)
    if int(n/2) ==0:
        return n
    return calc(int(n/2))

calc(10)

  :
10
5
2
1

再帰的なプロパティ:
  • には、明確な終了条件
  • が必要である.
  • より深い再帰に入るたびに、問題の規模は前回の再帰よりも
  • 減少しなければならない.
  • の再帰効率は高くなく、再帰階層が多すぎるとスタックオーバーフロー(コンピュータでは、関数呼び出しはスタック(stack)というデータ構造によって実現され、1つの関数呼び出しに入るたびにスタックフレームが追加され、関数が戻るたびにスタックフレームが減少する.スタックのサイズは無限ではないため、再帰呼び出しの回数が多すぎるとスタックオーバーフローを招く)
  • 再帰関数の実際の応用例、二分検索
    data = [1, 3, 6, 7, 9, 12, 14, 16, 17, 18, 20, 21, 22, 23, 30, 32, 33, 35]
    
    def binary_search(dataset,find_num):
        print(dataset)
    
        if len(dataset) >1:
            mid = int(len(dataset)/2)
            if dataset[mid] == find_num:  #find it
                print("    ",dataset[mid])
            elif dataset[mid] > find_num :#     mid  
                print("    mid[%s]  " % dataset[mid])
                return binary_search(dataset[0:mid], find_num)
            else:#     mid  
                print("    mid[%s]  " % dataset[mid])
                return binary_search(dataset[mid+1:],find_num)
        else:
            if dataset[0] == find_num:  #find it
                print("     ",dataset[0])
            else:
                print("    ,     [%s]     " % find_num)
    
    binary_search(data,66)

    2.匿名関数
    匿名関数とは明示的な指定を必要としない関数です
    #    
    def calc(n):
        return n**n
    print(calc(10))
    
    #      
    calc = lambda n:n**n
    print(calc(10))

    匿名関数は主に他の関数と組み合わせて使用され、以下のようになります.
    res = map(lambda x:x**2,[1,5,7,4,8])
    for i in res:
        print(i)