Java/Python/Mathematica中的递归序列

Question

你怎么用下面这些语言写出这个语句？

a(0) = 1
a_(n+1) = 1 - 1 / ( a_n + 3)

我需要找到最小的 n 值，使得 a_n -> 0.732050...。

我在Mathematica中的尝试

a[(x+1)_] = 1 - 1/(a[x_] + 3)

问题显然出在这个 a[(x+1)_] 上。
不过，我不知道怎么在Mathematica中以迭代的方式来做这件事。

Answer 1

Java是一种编程语言，常用于开发各种应用程序。它的特点是可以在不同的设备上运行，像手机、电脑等都可以用Java写的程序。

double A = 1;
int n = 0;
while (true) {
  System.out.println(n + " " + A);
  A = 1 - 1 / (A + 3);
  n++;
}

Python也是一种编程语言，特别适合初学者。它的语法简单明了，很多人用它来做数据分析、网站开发和人工智能等。

A = 1.0
n = 0
while 1:
  print n, A
  A = 1 - 1 / (A + 3)
  n += 1

Answer 2

Mathematica

a[0] = 1;
a[n_] := a[n] = 1 - 1/(a[n-1] + 3)

（注意这个记忆化技巧。）

另外，a[n] 很快会收敛到 sqrt(3)-1：

Solve[x == 1 - 1/(x+3), x]

Answer 3

Python，最简单的：

def a(n):
  if n == 0: return 1
  return 1 - 1 / float(a(n-1) + 3)

# limit is sqrt(3) - 1
limit = 3.0 ** 0.5 - 1.0

# get 9 digits' precision
i = 0
while abs(a(i) - limit) > 1.0e-9:
  i += 1

print i

这个代码输出了 8，这说明像递归消除或者记忆化这样的优化可能并不必要。

当然，通常我们想要的是通过数值来获取极限值，而不是通过分析的方法，所以正常的循环方式会有所不同——而且最好用一个高阶函数来封装...：

# get a function's limit numerically
def limit(f, eps=1.0e-11):
  previous_value = f(0)
  next_value = f(1)
  i = 2
  while abs(next_value - previous_value) > eps:
    previous_value = next_value
    next_value = f(i)
    i += 1
  return next_value

比较复杂的循环逻辑通常最好用生成器来封装：

def next_prev(f):
  previous_value = f(0)
  i = 1
  while True:
    next_value = f(i)
    yield next_value, previous_value
    i += 1
    previous_value = next_value

借助这个生成器，limit 的高阶函数变得简单多了：

def limit(f, eps=1.0e-11):
  for next_value, previous_value in next_prev(f):
    if abs(next_value - previous_value) < eps:
      return next_value

注意这种分离是多么有用：next_prev 表达了“获取函数的下一个和上一个值”的概念，而 limit 只处理“循环应该什么时候结束”。

最后但同样重要的是，itertools 通常是生成器的一个不错替代品，它可以让你以快速的方式封装复杂的迭代逻辑（不过这需要一些适应...;-）：

import itertools

def next_prev(f):
  values = itertools.imap(f, itertools.count())
  prv, nxt = itertools.tee(values)
  nxt.next()
  return itertools.izip(prv, nxt)