java - 计算没有变量的递归调用

Question

是否可以计算没有变量的递归深度？

Answer 1

在java中，

Thread.currentThread().getStackTrace()

可用于确定调用深度。递归调用的数量是堆栈长度和第一帧位置之间的差异。

或抛出异常，然后从最顶层的函数中检索堆栈：

Throwable.getStackTrace()

返回堆栈跟踪元素的数组，每个元素代表一个堆栈帧。数组的第零个元素（假设数组的长度不为零）表示堆栈的顶部，这是序列中的最后一个方法调用。通常，这是这个 throwable 被创建和抛出的点。数组的最后一个元素（假设数组的长度不为零）表示堆栈的底部，这是序列中的第一个方法调用。

http://docs.oracle.com/javase/1.4.2/docs/api/java/lang/Throwable.html

Answer 2

你在寻找这样的东西吗？

public int foo(int count) {
    if (exitCondition) return count; 
    foo(count+1);
}

计算调用的其他方法将涉及反射或使用字节码修改库（即 AoP）。

Answer 3

你的问题非常模糊，所以我做了几个假设：

1. “递归调用次数”是指“递归深度”
2. 函数的原始调用者想知道深度，所以递归方法返回它
3. 通过“无变量”，这意味着您甚至不能使用局部变量来跟踪深度

因此，如果您使用某种随机方法并调用递归函数：

public void randomMethod() {
    Something somethingToRecurseOn = ... ;
    int depth = recurse(somethingToRecurseOn);
}

这是我的解决方案的预期用途。这是recurse方法：

public int recurse(Something s) {
    Something subS = s.getSubS();
    if (subS == null) { // Exit condition
        return 1;
    }
    // Do something with subS
    return recurse(subS) + 1;
}

您将深度集成到函数的返回值中，并为退出条件假设深度为 1。

这实际上与我过去问过的一个面试问题有关，您必须在递归序列中返回元素的数量，签名是：

public int collatz(int n)

n您正在操作以查找序列的下一个数字的数字在哪里，该数字在 1 处停止。如果它是用递归而不是迭代实现的，它本质上会返回递归深度。