Code Eatアルゴリズムのクラシックコース聞いて整理した文章.
不正確な内容や漏れがある場合がありますので、講義をお勧めします.
再帰関数の2つの要素

Recursive case:現在の問題が大きすぎると、同じ形式のより小さい部分の問題を再帰的に解決する

Base case:問題が十分小さいなら、もっと小さい部分に分けなくてもすぐに答えがわかる

再帰関数を練習するときは、上記の2つの要素を書き出してから問題を解きます.

フィボナッチ数列

質問する

フィボナッチ数列とは,第1項と第2項が1であり,第3項からは前2項の和で定義された数列である.
例えば、第3項は第1項(1)と第2項(1)が加算された2であり、第4項は第2項(1)と第3項(2)が加算された3である.このように、フィボナッチ数列の上位10項は、1、1、2、3、5、8、13、21、34、55である.
パラメータを用いて1つ以上の自然数nを得、n番目のフィボナッチ数を返す再帰関数fibを書く.複文を書くことができません.

# n번째 피보나치 수를 리턴
def fib(n):
    # 코드를 입력하세요.

# 테스트: fib(1)부터 fib(10)까지 출력
for i in range(1, 11):
    print(fib(i))

# 콘솔 출력
1
1
2
3
5
8
13
21
34
55

に答える

fib(1)=1fib(1) = 1fib(1)=1
fib(2)=1fib(2) = 1fib(2)=1
fib(3)=fib(1)+fib(2)fib(3) = fib(1) + fib(2)fib(3)=fib(1)+fib(2)
fib(4)=fib(2)+fib(3)fib(4) = fib(2) + fib(3)fib(4)=fib(2)+fib(3)
.........
fib(n)=fib(n−2)+fib(n−1)fib(n) = fib(n-2) + fib(n-1)fib(n)=fib(n−2)+fib(n−1)
したがって、basecaseとrecursive caseは次のようにエクスポートされます.
n<=2→fib(n)=1n<=2\rightarrow fib(n)=1n<=2→fib(n)=1
n>2→fib(n)=fib(n−2)+fib(n−1)n>2\rightarrow fib(n)=fib(n-2)+fib(n-1)n>2→fib(n)=fib(n−2)+fib(n−1)

コード#コード#

# n번째 피보나치 수를 리턴
def fib(n):
    # base case
    if n == 1:
        return 1
    elif n == 2:
        return 1
    # recursive case
    return fib(n-2) + fib(n-1)

# 테스트: fib(1)부터 fib(10)까지 출력
for i in range(1, 11):
    print(fib(i))

# 콘솔 출력
1
1
2
3
5
8
13
21
34
55

数値と

質問する

nnnの2番目の三角数(三角形数)は自然数1〜nnnの和である.パラメータで整数値nを取得し、再帰関数triangle numberを作成してnnn番目の三角数を返します.nnは111以上の自然数を仮定する.複文を書くことができません.

# 1부터 n까지의 합을 리턴
def triangle_number(n):
    # 코드를 입력하세요

# 테스트: triangle_number(1)부터 triangle_number(10)까지 출력
for i in range(1, 11):
    print(triangle_number(i))

# 콘솔 출력
1
3
6
10
15
21
28
36
45
55

に答える

tn(1)=1tn(1) = 1tn(1)=1
tn(2)=1+2=tn(1)+2=3tn(2) = 1 + 2 = tn(1) + 2 = 3tn(2)=1+2=tn(1)+2=3
tn(3)=1+2+3=tn(2)+3=6tn(3) = 1 + 2 + 3 = tn(2) + 3 = 6tn(3)=1+2+3=tn(2)+3=6
tn(4)=1+2+3+4=tn(3)+4=10tn(4) = 1 + 2 + 3 + 4 = tn(3) + 4 = 10tn(4)=1+2+3+4=tn(3)+4=10
.........
tn(n)=tn(n−1)+ntn(n) = tn(n-1) + ntn(n)=tn(n−1)+n
したがって、basecaseとrecursive caseは次のようにエクスポートされます.
n=1→tn(n)=1n=1\rightarrow tn(n)=1n=1→tn(n)=1
n>1→tn(n)=tn(n−1)+nn>1\rightarrow tn(n)=tn(n-1)+nn>1→tn(n)=tn(n−1)+n

コード#コード#

# 1부터 n까지의 합을 리턴
def triangle_number(n):
    # base case
    if n == 1:
        return 1
    # recursive case
    return triangle_number(n-1) + n 
    
# 테스트: triangle_number(1)부터 triangle_number(10)까지 출력
for i in range(1, 11):
    print(triangle_number(i))

数値と

質問する

パラメータで整数nを受信し、nビット数の和を返す再帰関数sum digitalsを作成します.繰り返し文を書くことができません.

# n의 각 자릿수의 합을 리턴
def sum_digits(n):
    # 코드를 작성하세요.

# 테스트
print(sum_digits(22541))
print(sum_digits(92130))
print(sum_digits(12634))
print(sum_digits(704))
print(sum_digits(3755))

# 콘솔 출력
14
15
16
11
20

に答える

sd(22541)=sd(2254)+1sd(22541) = sd(2254) + 1sd(22541)=sd(2254)+1
sd(2254)=sd(225)+4sd(2254) = sd(225) + 4sd(2254)=sd(225)+4
sd(225)=sd(22)+5sd(225) = sd(22) + 5sd(225)=sd(22)+5
sd(22)=sd(2)+2sd(22) = sd(2) + 2sd(22)=sd(2)+2
sd(2)=2sd(2) = 2sd(2)=2
...
sd(n)=sd(nを10で割る)+nを10で割る残りのsd(n)=sd(nを10で割る)+nを10で割る残りのsd(n)=sd(nを10で割る)+nを10で割る
したがって、basecaseとrecursive caseは次のようにエクスポートされます.
n<10→sd(n)=nn < 10\rightarrow sd(n) = nn<10→sd(n)=n
n≧10→sd(nを10で割った分)+nを10で割った残りngeq 10righarrowsd(nを10で割った分)+nを10で割った残りn≧10→sd(nを10で割った分)+nを10で割った残りn

コード#コード#

# n의 각 자릿수의 합을 리턴
def sum_digits(n):
    # base case
    if n < 10:
        return n
    # recursive case
    return sum_digits(n // 10) + n % 10

# 테스트
print(sum_digits(22541))
print(sum_digits(92130))
print(sum_digits(12634))
print(sum_digits(704))
print(sum_digits(3755))

# 콘솔 출력
14
15
16
11
20