递归相关题

遵循四个原则，

1) 程序执行一个函数时，就创建一个新的受保护的独立空间(新函数栈)

2) 函数的局部变量是独立的，不会相互影响

3) 递归必须向退出递归的条件逼近，否则就是无限递归，死龟了:)

4) 当一个函数执行完毕，或者遇到 return，就会返回，遵守谁调用，就将结果返回给谁。

斐波那契数列

请使用递归的方式，求出斐波那契数 1,1,2,3,5,8,13... 给你一个整数 n，求出它的斐波那契数是多少？

int F(int x) {
  if (x == 1 || x == 2) {
    return 1;
  }
  return F(x - 1) + F(x - 2);
}

猴子吃桃子问题

有一堆桃子，猴子第一天吃了其中的一半，并再多吃了一个！以后每天猴子都吃其中的一半，然后再 多吃一个。当到第十天时，想再吃时（还没吃），发现只有 1 个桃子了。问题：最初共多少个桃子？

// 第十天 1
// 第九天 (1+1)*2
// 第八天 ((1+1)*2+1)*2
int f(int x) {
  if (x == 10) {
    return 1;
  }
  return (f(x + 1) + 1) * 2;
}

个人思考：

递归就是栈的先入后出思路，跟深度优先遍历类似，找到最深处的解，出栈（将解带出到下面的栈），再接着出栈，直到栈出完，也就算出最开始的解

递归是有规律的，没有规律的也不是递归

可以看看深度优先遍历的讲解，对栈的出和入有清晰的了解后，递归也就顺理成章的知道原理了

见：浅析深度优先和广度优先遍历实现过程、区别及使用场景