Haskell无限递归 [英] Haskell infinite recursion

问题描述

以下函数计算斐波那契数列:

The following function computes the Fibonacci sequence:

fib = 0 : 1 : (zipWith (+) fib (tail fib))

如果运行它，我们将获得一个无限列表，但是递归如何工作?如果该函数不断调用自身，为什么会在屏幕上打印数字?如果您能解释一下编译器如何管理调用，我将不胜感激.

If we run it, we will get an infinite list, but how does the recursion work? Why does it get to print numbers on the screen if it the function keeps calling itself? I would appreciate if you could explain how the compiler manages the calls.

推荐答案

我画了一幅画，可能会对您有所帮助.
请注意zipWtih op (x:xs) (y:xs) = (op x y):zipWith xs ys，这是zipWtih沿列表右移的方式.它正在读取元素并吐出总和:

I've drawn a picture, which you might find helpful.
Note that zipWtih op (x:xs) (y:xs) = (op x y):zipWith xs ys, which is how zipWtih appears to "move" right along the list. It's reading elements and spitting out sums:

这里是更详细的分步评估. (尽管我将粘贴其中的副本，但内存中只有一个副本.)对于不麻烦写出来的事情，我将使用....来完成.

Here's a more detailed step-by-step evaluation. (Although I'll paste copies of what's there, there's only one copy in memory.) I'll use .... for things I can't be bothered to write out.

fib = 0:1:zipWith (+) fib (tail fib)
    = 0:1:zipWith (+) (0:1: .... ) (tail (0:1: .... )
    = 0:1:(0+1:zipWith (+) (1:(0+1: .... )) ( 0+1:..... ))
    = 0:1:1:zipWith (+) (1: ....) (......)

注意，现在我们知道了zipWith (+) fib (tail fib) = 1:......

notice that now we know that zipWith (+) fib (tail fib) = 1:......

    = 0:1:1:zipWith (+) (1:1: ....) (1:......)
    = 0:1:1:(1+1):zipWith (+) (1:(1+1): .....) ((1+1):....)
    = 0:1:1:2:zipWith (+) (1:2: .....) (2:....)

我会快一点:

    = 0:1:1:2:(1+2):zipWith (+) (2: .....) (....)
    = 0:1:1:2:3     :zipWith (+) (2:3 .....) (3:....)
    = 0:1:1:2:3:(2+3):zipWith (+) (3:(2+3):.....) ((2+3):.....)
    = 0:1:1:2:3:5     :zipWith (+) (3:5:.....) (5:.....)
    = 0:1:1:2:3:5:8    :zipWith (+) (5:8:....) (8:......)
    = 0:1:1:2:3:5:8:13  :zipWith (+) (8:13:....) (13:......)
    = 0:1:1:2:3:5:8:13:21:zipWith (+) (13:21....) (21:......)

在每个阶段，zipWith函数的最后两个参数就像指向指针的指针(一个位置和两个位置)在fib列表中比当前位置更远.

At each stage, the last two arguments to the zipWith function are like pointers to (one and two positions) further up the fib list than we are at present.

这篇关于Haskell无限递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！