LeetCode 题解：69. x 的平方根，牛顿迭代法 + 递归，JavaScript，详细注释

原题链接：https://leetcode-cn.com/problems/sqrtx/

解题思路：

1. 要理解牛顿迭代法，我们需要先回顾一下导数，或者可以看这一篇[导数入门](https://www.shuxuele.com/calculus/derivatives-introduction.html)。

2. 题解参考了二分查找 + 牛顿法（Python 代码、Java 代码）、[牛顿迭代法](https://leetcode-cn.com/problems/sqrtx/solution/niu-dun-die-dai-fa-by-loafer/)、[69. x 的平方根-二分查找, 牛顿法](https://leetcode-cn.com/problems/sqrtx/solution/69-x-de-ping-fang-gen-er-fen-cha-zhao-niu-dun-fa-b/)。

3. 根据题意，该题是这样一个方程 $x^{2}=a$，已知 $a$求 $x$。可以将其用函数 $f(x)=x^{2}-a$代替。

4. 这个函数的导数是 $2x$，也就是 $2x0=\cfrac{f(x)-f(x0)}{x-x_0}$。

5. 将 $f(x)=0$带入，可以得到 $2x0=\cfrac{-f(x0)}{x-x_0}$。

6. 将 $f(x0)=x0^{2}-a$带入，可以得到 $2x0=\cfrac{a-x0^{2}}{x-x_0}$。

7. 将等式整理，可以得到 $x=\cfrac{x0+\cfrac{a}{x0}}{2}$。

/** * @param {number} x * @return {number} */var mySqrt = function (x) {  function sqrt(x0) {    // 当遇到第一个x0 * x0 <= x的值时，表示已经得到最接近的结果，将x0的整数部分返回即可    // 用Math.floor将x0*x0向下取整    // 避免例如TestCase: 5，会出现x0 * x0=5.000000000000001，造成死循环    if (Math.floor(x0 * x0) <= x) {      return Math.floor(x0);    }
    // 套用分析得到的迭代公式，计算出新的x0    x0 = (x0 + x / x0) / 2;
    return sqrt(x0);  }
  return sqrt(x);};