关于递归算法x(x(8))需要调用几次函数x(int n)

我就是我 2022-07-12 07:37 200阅读 0赞

好久没有写博客了~最近去搞ios了，都没有时间研究我的unity3d![哭][cry.gif]~~~

今天看到一个面试题，蒙圈了~

这道题是关于递归算法的，好在姐姐聪明机智搞明白了![生气][mad.gif]

下面把我的想法和做法分享给大家，希望对像我酱紫的 小白有点作用![奋斗][struggle.gif]

**原题目：设计递归[算法][Link 1]x(x(8))需要调用几次函数x(int n)。**

class program
     {
         static void Main(string[] args)
         {
             int i;
             i = x(x(8));
         }
         static int x(int n)
         {
             if (n <= 3)
                 return 1;
             else
                 return x(n - 2) + x(n - 4) + 1;
         }
     }

**答案解析：**x(x(8))的结果是9，函数x(int n)被调用了18次。

首先先看x(8),代入函数：

x(8) = x(6) +x(4) +1

= x(4) + x(2) +1 + x(2) + x(0) +1 + 1

= x(2) + x(0) +1 + 1 + 1 +1 + 1 +1 + 1

= 9，函数x(int n)被调用了9次

那么，x(x(8))=x(9),代入函数：

x(9) = x(7) +x(5) +1

= x(5) + x(3) +1 + x(3) + x(1) +1 + 1

= x(3) + x(1) +1 + 1 + 1 +1 + 1 +1 + 1

= 9，函数x(int n)被调用了9次

用二叉树的思想理解比较简单，如图所示：

![Center][]

9次+9次=18次。所以函数x(int n)被调用了18次。

其实搞明白挺简单的![大笑][laugh.gif]

[cry.gif]: /images/20220711/b86d4d331f1845ddb8fb9ef02c583621.png
[mad.gif]: /images/20220711/160dc0a6237144a0823a4c78442c9c5e.png
[struggle.gif]: /images/20220711/e65dd968a7b34f4b93b6998ade1eb34f.png
[Link 1]: http://lib.csdn.net/base/datastructure
[Center]: /images/20220711/df8e73ec2ed547a5b96952cc970ac94f.png
[laugh.gif]: /images/20220711/4ef3d47c675348c99ef7d0f72f9d60d8.png