递归方法的运行时间

Question

我已经编写了一个方法的伪代码来计算Pascal三角形第i行中的一个入口。

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的几个例子中找到一个证明应该很容易。