面接準備/アルゴリズム6/再帰用法

再帰呼び出し

高度なソートアルゴリズムを使用するため、高度なソートアルゴリズムを学習する前に、再帰アルゴリズムを学習します.

1.再帰コール（recursive call、再帰コール）

関数で同じ関数を呼び出す形式:

は多くのアルゴリズムに使用され、

を熟知する必要がある.

2.再帰的用法の理解

再帰的使用法について説明する

例

例

Recursive Call生成アルゴリズム

ファクトリ

を使用

例-分析

簡単な状況から考える

2! = 1 X 2

3! = 1 X 2 X 3

4! = 1 X 2 X 3 X 4 = 4 X 3!

ルールが表示されます:n!=n X (n - 1)!

関数を作成します.

関数(n)がn>1の場合はnX関数(n-1)

を返す.

関数(n)はn=1でreturn

を表す.

検証(コード検証ではなく、直接簡単な状況から検証)

先2!

関数(2)であれば2 X関数(1)は2>1である

関数(1)は1で、2 X 1=2ペアを返します!

先3!

関数(3)の場合、3>1は3 X関数(2)である

関数(2)は最終的に1番2にされます!は、2 X 1=2

を返します.

3 X関数(2)=3×2=3×2×1=6対!

先4!

関数(4)の場合、4>1は4 X関数(3)である

関数(3)は最終的に2回3×2×1=6

である.

4 X関数(3)=4 X 6=24対!

例-コード・レベルでの書き込み

def factorial(num):
    if num > 1:
        return num * factorial(num - 1)
    else:
        return num

for num in range(10):
    print (factorial(num))

0
1
2
6
24
120
720
5040
40320
362880

例-時間の複雑さと空間の複雑さ

階乗(n)n-1次階乗()関数を呼び出して乗算する

は、n-1番繰り返し文を呼び出すのと同じ

である.

階乗()関数が呼び出されるたびに、領域変数n

が生成される.

時間的複雑度/空間的複雑度はO(n−1)であるため,両者ともO(n)である.

3.再帰呼び出しの一般形式

# 일반적인 형태1
def function(입력):
    if 입력 > 일정값: # 입력이 일정 값 이상이면
        return function(입력 - 1) # 입력보다 작은 값
    else:
        return 일정값, 입력값, 또는 특정값 # 재귀 호출 종료

# 일반적인 형태2
def function(입력):
    if 입력 <= 일정값:              # 입력이 일정 값보다 작으면
        return 일정값, 입력값, 또는 특정값              # 재귀 호출 종료
    function(입력보다 작은 값)
    return 결과값

def factorial(num):
    if num <= 1:
        return num
    
    return num * factorial(num - 1)

for num in range(10):
    print (factorial(num))

0
1
2
6
24
120
720
5040
40320
362880

再帰呼び出しはスタックの典型的な例です

関数は内部スタックのように管理されます.

もし私が

の復帰コールを理解しなかったら?-コード解析

注意:Pythonでは、再帰関数の深さは(1回の呼び出し...)です.1000回未満

4.再帰的用法を用いたプログラミング練習

プログラミング練習
再帰関数で次の関数を完了し、1からnumの積を出力します.

def muliple(data):
    if data <= 1:
        return data
    
    return -------------------------
    
multiple(10)

def multiple(num):
    return_value = 1
    for index in range(1, num + 1):
        return_value = return_value * index
    return return_value

def multiple(num):
    if num <= 1:
        return num
    return num * multiple(num - 1)

multiple(10)

3628800

プログラミング練習
数値を含むリストを指定すると、リストの和を返す関数を作成します.

참고: 임의 값으로 리스트 만들기 random.sample(0 ~ 99까지 중에서, 임의로 10개를 만들어서 10개 값을 가지는 리스트 변수 만들기
import random 
data = random.sample(range(100), 10)

import random 
data = random.sample(range(100), 10)
data

[72, 50, 8, 38, 77, 32, 90, 48, 74, 79]

プログラミング練習
数値を含むリストを取得する場合は、リストの和(再帰関数を書く)を返す関数を作成します.

def sum_list(data):
    if len(data) == 1:
        return data[0]
    
    return --------------------------------
import random

data = random.sample(range(100), 10)

print (sum_list(data))

def sum_list(data):
    if len(data) <= 1:
        return data[0]
    return data[0] + sum_list(data[1:])

sum_list(data)

568

プログラミング練習
回文とは、逆順で読んでも正しく読める単語や文のこと.
リストスライドを使用して、返信を判別できる関数を作成します.

참고 - 리스트 슬라이싱
string = 'Dave' 
string[-1] --> e
string[0] --> D
string[1:-1] --> av
string[:-1] --> Dav

def palindrome(string):
    if len(strung) <= 1:
        return True
    
    if string[0] == string[-1]:
        return palindrome(string[1:-1])
    else:
        return False

プログラミング練習
1、整数nについて
2.nが奇数なら3×n+1、
3.nが偶数の場合、nは2で除算される.
4.nが最終的に1になるまで、2と3のプロセスを繰り返す.
例えば、nに3を入れると、

3
10
5
16
8
4
2
1

이 됩니다.

이렇게 정수 n을 입력받아, 위 알고리즘에 의해 1이 되는 과정을 모두 출력하는 함수를 작성하세요.

def func(n):
    print (n)
    if n == 1:
        return n
    
    if n % 2 == 1:
        return (func((3 * n) + 1))
    else:
        return (func(int(n / 2)))
        
        

func(3)

3
10
5
16
8
4
2
1





1

プログラミング練習

문제: 정수 4를 1, 2, 3의 조합으로 나타내는 방법은 다음과 같이 총 7가지가 있음
1+1+1+1
1+1+2
1+2+1
2+1+1
2+2
1+3
3+1
정수 n이 입력으로 주어졌을 때, n을 1, 2, 3의 합으로 나타낼 수 있는 방법의 수를 구하시오

힌트: 정수 n을 만들 수 있는 경우의 수를 리턴하는 함수를 f(n) 이라고 하면,

f(n)은 f(n-1) + f(n-2) + f(n-3) 과 동일하다는 패턴 찾기

출처: ACM-ICPC > Regionals > Asia > Korea > Asia Regional - Taejon 2001

練習帳に問題解析を作成する例

def func(data):
    if data == 1:
        return 1
    elif data == 2:
        return 2
    elif data == 3:
        return 4
    
    return func(data -1) + func(data - 2) + func(data - 3)

func(5)

13