澄清尾部递归方法

发布于 2025-02-07 12:04:27 字数 319 浏览 1 评论 0原文

以下方法是尾巴恢复性吗？

我相信它不是尾随的递归，因为它依赖于先前的结果，因此需要一个堆栈框架，我是否正确地说明这一点？

public int[] fib(int n)
{
    
    if(n <= 1){
        return (new int[]{n,0});
    }
    else{
        int[] F = fib(n-1);
        return (new int[]{F[0]+ F[1], F[0]});
    }
}

原文

Is the following method tail-recursive?

I believe that it is not tail recursive because it relies on the previous results and so needs a stack frame, am I correct to state this?

public int[] fib(int n)
{
    
    if(n <= 1){
        return (new int[]{n,0});
    }
    else{
        int[] F = fib(n-1);
        return (new int[]{F[0]+ F[1], F[0]});
    }
}

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

枫林﹌晚霞¤ 2025-02-14 12:04:27

您是正确的：这不是尾部递归，因为最后一行不是形式

return funcName(args);

You are correct: It is not tail recursive because the last line is not of the form

return funcName(args);

回复收藏 0 原文

染年凉城似染瑾 2025-02-14 12:04:27

是的，您是正确的，因为它不会以将

return fib(somevalue);

其转换为尾部回复版本的形式而结束，因此您可以执行

// Tail Recursive
// Fibonacci implementation
 
class GFG
{
    // A tail recursive function to
    // calculate n th fibonacci number
    static int fib(int n, int a, int b )
    {
         
        if (n == 0)
            return a;
        if (n == 1)
            return b;
        return fib(n - 1, b, a + b);
    }
     
    public static void main (String[] args)
    {
        int n = 9;
        System.out.println("fib(" + n +") = "+
                                 fib(n,0,1) );
    }
}

从 https://www.geeksforgeeks.org/tail-recursion-fibonacci/

Yes, you are correct, since it does not end with a call to itself of the form of

return fib(somevalue);

To convert it into a tail-recursive version you could do something like

// Tail Recursive
// Fibonacci implementation
 
class GFG
{
    // A tail recursive function to
    // calculate n th fibonacci number
    static int fib(int n, int a, int b )
    {
         
        if (n == 0)
            return a;
        if (n == 1)
            return b;
        return fib(n - 1, b, a + b);
    }
     
    public static void main (String[] args)
    {
        int n = 9;
        System.out.println("fib(" + n +") = "+
                                 fib(n,0,1) );
    }
}

Code taken from https://www.geeksforgeeks.org/tail-recursion-fibonacci/

回复收藏 0 原文

~没有更多了~