재귀 함수는 실행 흐름이 Bottom - Up이다
이 말은 하위 문제들을 풀면서 최종값이 산출된다는 것이다.
Stack는 Last In First Out, 즉 LIFO 구조이다.
구체적인 설명을 위해서 트리를 예시로 들어 보자.
그 트리는 피보나치 함수를 재귀 함수로 구현했을 떄의 실행 과정을 나타내고 있다고 하자.
Fibonachi( 10 )을 구하기 위해서는 트리의 정점에서부터 아래로 내려간다.
그 이유는 Fibonachi( 10 )을 구하기 위해서는 하위 문제 , 즉 Fibonachi(1),(2),(3) 등을 풀어야 하기 때문이다.
즉, 상위 문제를 풀기 위해서는 가장 마지막의 하위 문제(가장 마지막에 push된 데이터)를 풀고, 점진적으로 가장 상위의
문제(가장 이전에 push된 데이터) 순의 실행 흐름을 가진다.
고로, 재귀 함수는 Stack으로도 구현이 가능하다.
'알고리즘(アルゴリズム） > 알고리즘 이모저모(アルゴリズムの緒論)' 카테고리의 다른 글
| pre-condition을 고려하며 function 작성하자!!!! (0) | 2023.01.28 |
|---|---|
| 합동식(modular)을 왜 쓰는 걸까??? (0) | 2023.01.28 |
| 고정된 데이터들의 탐색 vs 회전하는 데이터들의 탐색 (2) | 2023.01.26 |
| 재귀 함수(recursive function)에 대한 메뉴얼 (0) | 2023.01.26 |
| 재귀 함수(recursive function) with 꼬리 재귀(tail recursive) (0) | 2023.01.26 |
