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

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

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

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

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

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

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

  1. class program
  2.  {
  3.      static void Main(string[] args)
  4.      {
  5.          int i;
  6.          i = x(x(8));
  7.      }
  8.      static int x(int n)
  9.      {
  10.          if (n <= 3)
  11.              return 1;
  12.          else
  13.              return x(n - 2) + x(n - 4) + 1;
  14.      }
  15.  }

答案解析：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次。

其实搞明白挺简单的大笑

发表评论

表情：
评论列表 （有 0 条评论，229人围观）

还没有评论，来说两句吧...

相关阅读

    相关 递归调用函数

    递归调用 递归调用 一、什么叫做函数的递归调用？ 函数直接或间接的调用自己就是函数的递归调用。 【函数调用自己】 二、【算法1】通过函数的递归调用计算n!

    傷城~傷城~/ 0 赞/ 82 阅读