[DFS/BFS]再帰関数:::必要なデータ構造基礎
さいきかんすう
自分の関数を再呼び出し
再帰関数の終了条件
再帰関数を解題で使用する場合は,再帰関数がいつ終了するか,終了条件を明確にしなければならない.次のコードは、100回の再帰関数を呼び出すように記述されています.
def recursive_function(i):
# 100번째 호출을 했을 때 종료되도록 종료 조건 명시
if i == 100:
return
print(i, '번째 재귀함수에서', i + 1, '번째 재귀함수를 호출합니다.')
recursive_function(i + 1)
print(i, '번째 재귀함수를 종료합니다.')
recursive_function(1)
.
.
.
.
.
.
コンピュータ内部では、再帰関数の実行にはスタックデータ構造が使用される.関数の呼び出しを続行する場合、最後に呼び出された関数は、前の関数呼び出しを終了する前に完了する必要があります.
再帰関数を使用したファクトリの例
# 반복적으로 구현한 n!
def factorial_iterative(n):
result = 1
# 1부터 n까지의 수를 차례대로 곱하기
for i in range(1, n + 1):
result *= i
return result
# 재귀적으로 구현한 n!
def factorial_recursive(n):
if n <= 1: # n이 1 이하인 경우 1을 반환
return 1
# n! = n * (n - 1)!를 그대로 코드로 작성하기
return n * factorial_recursive(n - 1)
# 각각의 방식으로 구현한 n! 출력(n = 5)
print('반복적으로 구현:', factorial_iterative(5))
print('재귀적으로 구현:', factorial_recursive(5))
繰り返し文の代わりに再帰関数を使用する場合、
の利点は、より簡潔なコード
ユークリッドアーク除去法の最大公約数計算例
- ユークリッド湖製法
2つの自然数A,B,AをBで割ったものをRと呼ぶ.このとき、AとBの最大公約数は、BとRの最大公約数に等しい.
def gcd(a,b):
if a % b == 0:
return b
else:
return gcd(b, a%b)
print(gcd(192, 162))
運転結果
6
📘 これは就職のためのコードテストです。 ::chapter 05
Reference
この問題について([DFS/BFS]再帰関数:::必要なデータ構造基礎), 我々は、より多くの情報をここで見つけました https://velog.io/@ssongplay/DFSBFS-재귀함수-꼭-필요한-자료구조-기초テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol