如何找到递归算法的函数？

我的任务是“检查下面的代码并导出一个函数g（n），它对应于在调用方法moreMystery之后打印的整数的确切总数。”如何找到递归算法的函数？

我的问题是如何找到一个依赖于数组长度的函数？我希望看到答案，但对我来说更重要的是逐步解决方案中对答案的解释。

public void moreMystery (int [] data) { 
int n = data.length;     // find the length of the array 
moreMysteryContinued (data, n - 1); 
} 


private void moreMysteryContinued (int [] data , int i) { 
    if (i >= 0) { 
    System.out.print(data[i]); 
    moreMysteryContinued(data, i - 1); 
    moreMysteryContinued(data, i - 1); 
} 
}

来源

2017-09-27 roleveltv

你有什么想法？你有什么尝试？ – SDhaliwal

我了解递归如何工作，但这是我第一次遇到这种递归。我试图分析递归如何在特定情况下工作，并且当我看到它会执行每个首先更多的MyMyCendingContinued（数据，i-1）递归方法，直到遇到基本情况（i == -1），然后开始执行第二个从最小的数字i开始递归。 – roleveltv

我还计算了将为某个n数执行的打印量。例如：0 - > 0; 1 - > 1; 2 - > 3; 3-> 7; 4 - > 15.然而我不明白公式本身 – roleveltv

要开始我采取了打印语句计数，并试图从中推导出一个公式。

2^4 -1 = 16 -1 = 15 
2^3 -1 = 8 - 1 = 7 
2^2 -1 = 4 - 1 = 3

所以打印量的公式应该是2^n-1。

我会试着解释如何通过代码找到公式。

对于每次调用moreMysteryContinued它都会生成2个以上的打印语句。因此，对于n次调用MoreMysteryContinued，将会有2^n个打印语句。我不完全确定-1在哪里进来，但基于计算出来的2^n-1是整数公式的打印

来源

2017-09-27 05:23:18 FattySalami

感谢您的解答和解释！将尝试追踪它并理解-1从哪里来。但总的来说，这个公式正是我想要找到的。 – roleveltv

如何找到递归算法的函数？

回答

相关问题