编程算法 - 阶乘跟Fibonacci数列(递归) 代码(C)

编程算法 - 阶乘和Fibonacci数列(递归) 代码(C)

阶乘和Fibonacci数列(递归) 代码(C)

本文地址: http://blog.****.net/caroline_wendy

递归的基础, 实现阶乘和Fibonacci数列, fib数列可以通过动态规划, 减少计算次数.

代码:

/*
 * main.cpp
 *
 *  Created on: 2014.7.13
 *      Author: Spike
 */

/*eclipse cdt, gcc 4.8.1*/

#include <stdio.h>

using namespace std;

int fact(int n) {
	if (n==0)
		return 1;
	return n*fact(n-1);
}

int fib(int n) {
	if (n<=1) return n;
	return fib(n-1)+fib(n-2);
}

int fib_memo(int* memo, int n) {
	if (n<=1) return n;
	if (memo[n]!=0) return memo[n];
	return memo[n] = fib(n-1)+fib(n-2);
}


int main(void)
{
	int result_fib = fib(6);
	printf("result_fib = %d\n", result_fib);

	const int MAX_N = 20;
	int memo[MAX_N+1];
	for (int i; i<MAX_N+1; ++i)
		memo[i] = 0;

	int result_fib_memo = fib_memo(memo, 6);
	printf("result_fib_memo = %d\n", result_fib_memo);

    return 0;
}

输出:

result_fib = 8
result_fib_memo = 8