第三章 函数和递归(4)

【例题】求n的阶乘

int factorial(int n) {
	if(n <= 1)
		return 1;
	return n*factorial(n-1);
}

【例题】求第n个斐波那契数（不考虑溢出）

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

用while循环求斐波那契数列

int fib(int n) {
	int a = 1;
	int b = 1;
	int c = 1;

	while(n > 2) {
		c = a + b;
		a = b;
		b = c;
		n--;
	}
	return c;
}

【例题】青蛙跳台阶：

算法步骤：

1. 当只有1层台阶时：有一种跳法
2. 当有两层台阶时：有两种跳法
3. 当有三层台阶时：可以先跳一层，这时还有两层台阶要跳，说明有两种跳法。也可以先跳两层，这样有一种跳法。一共有三种跳法
4. 当有n层台阶时：有$fib(n)=fib(n-1)+fib(n-2)$种跳法

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