피보나치 수열에서는 앞의 두 개의 숫자를 더해서 뒤의 숫자를 만든다. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55... int fib(int n) { if( n==0 ) return 0; if( n==1 ) return 1; return (fib(n-1) + fib(n-2)); } 이 코드를 이용해서 fib(6)를 실행하면 fib()함수가 25번이나 호출된다. fib() 함수가 25번이나 호출된다. 중간에 계산되었던 값을 기억하지 않고 다시 계산하기 때문이다. fib(6) 1번 호출 fib(5) 1번 호출 fib(4) 2번 호출 fib(3) 3번 호출 fib(2) 5번 호출 fib(1) 8번 호출 시간복잡도 O(2^n) 따라서 n이 커지면 커질수록 엄청난 순환호출이 필요하게 된다. 그..

■ 재귀적 거듭제곱 계산 구현 C언어로 재귀(순환, recursion)적 거듭제곱 계산을 구현하면 다음과 같다. double power(double x, int n) { if (n == 0) return 1; else if ((n % 2) == 0) return power(x * x, n / 2); else return x * power(x * x, (n - 1) / 2); } 결과값을 볼 수 있는 전체 실행코드 #include double power(double x, int n) { if (n == 0) return 1; else if ((n % 2) == 0) return power(x * x, n / 2); else return x * power(x * x, (n - 1) / 2); } int ma..

■ 팩토리얼 구현 C언어로 재귀(순환, recursion)적 팩토리얼을 구현하면 다음과 같다. int factorial(int n) { if (n