algorithm - 递归方法的运行时间

Question

我已经为计算帕斯卡三角形的第 i 行第 j 行中的条目的方法编写了伪代码。

Pascal(i,j)
  if(i==j or j==0)
     return 1;
  return Pascal(i-1,j-1) + Pascal(i-1,j)

我的问题是我无法弄清楚运行时间。我知道它是指数的，但我不知道如何通过解决递归关系来证明它。

Answer 1

你最好想出几个例子来看看你走了多远。请记住，您有一个三角形。你从第 i 行开始，然后你在第 i-1 行。在下一步，您在第 i-2 行。等等。在最坏的情况下，您必须返回多少行？

画图并做例子来建立直觉。从几个 i=6 的例子中找到一个证明应该很容易。