안녕하세요. 자바 재귀함수에 대해 질문합니다.

Question

public class Valuable{ public static int fibonacci(int number) { if(number>2) { return fibonacci(number-1)&#43; fibonacci(number-2); }else { return 1; } } public static void main(String[] args) { System.out.println(fibonacci(6)); } } 안녕하세요. 자바 시작한 지 얼마 되지 않아 많이 부족합니다. 그래서 아직 위에 식이 이해하려고 계속 찾아봤는데 저 식은 이해가 가질 않네요..ㅜㅜ 처음 number값을 6으로 넣고 아래에 -1과 -2에 들어가면 5랑 4가 생기고 그 다음은 왼쪽number -2의 값이 number>2에 충족하지 않아 생성이 되지 않고 오른쪽은 3까지 내려간다는 것 까지 이해를 했습니다. 그런데 왜 값이 8이 나오는 지는 도저히 이해가 가질 않습니다.. 여기 잘하는 분이 많이 계셔서 여쭤봅니다!

Kolin · Accepted Answer

와.. 주변에 물어볼 사람도 없어 고생했는데 진심으로 감사합니다. 덕분에 또 하나 알아가네요! 정말 감사합니다~ 다 복 받으실 거에요!!

Dive_Drink_Develope · Answer

fibonacci (1) ~ fibonacci (6) 까지 미리 구해놓고 시뮬레이션 깊이를 조절하면서 해보시면 이해될듯.8이 나오는 이유는 return 5 &#43; 3 이기때문이죠.

albear · Answer

f(6) &#61; f(5) &#43; f(4)f(5) &#61; f(4) &#43; f(3)f(4) &#61; f(3) &#43; f(2) f(3) &#61; f(2) &#43; f(1) f(2) &#61; f(1) &#43; f(0) 0과 1은 그대로 리턴이렇게 실행될텐데 아래에서부터 계산해 올라가면 조금 이해가 더 쉽습니다. 이렇게 아래에서부터 계산해 보면f(1) &#61; 1f(2) &#61; f(1) &#43; f(0) &#61;> 1 &#43; 0 &#61;> 1f(3) &#61; f(2) &#43; f(1) &#61;> 1 &#43; 1 &#61;> 2f(4) &#61; f(3) &#43; f(2) &#61;> 2 &#43; 1 &#61;> 3f(5) &#61; f(4) &#43; f(3) &#61;> 3 &#43; 2 &#61;> 5f(6) &#61; f(5) &#43; f(4) &#61;> 5 &#43; 3 &#61;> 8 참고로 구현하신 방식은 복잡도가 O(2^n) 으로써 효율적이지 못합니다.재귀함수를 실행하면서 이미 계산한걸 또 계산하고 하기 때문이죠.그래서 좀 더 효율적인 방법이 더 있는데 피보나치 문제에서는 단골로 나오니 같이 알아보시는것도 좋을것 같습니다.

Kolin · Answer

혹시 괜찮으시다면 제가 위랑 비슷한 예문을 여러개 써봤는데 제가 원하는 값의 return이 아닌 다른 return값을 1이 아닌 다른 수로 하니 제가 구하려는 return에 곱이 되어 값이 도출되었습니다. 제가 return값에 곱을 명령하지 않아도 그렇게 나오던데 혹시 그 이유가 어떻게 되는지 아시나요..?

Dive_Drink_Develope · Answer

albear 님이 계산하신대로 그 숫자를 넣고 f 1 부터 다시 계산해보세요

안녕하세요. 자바 재귀함수에 대해 질문합니다.

5개의 답변

#recursion 목록