什麼樣的編程語言會不支持遞歸呢？

01-04

我其實好奇很久了，因為我還記得我看的第一本編程書（是一本講C語言的書）上說「C語言是支持遞歸的」，也就是說遞歸應該是一個非普適的概念，也就是說一些語言是不支持遞歸的。
那麼為什麼會有編程語言不支持遞歸呢？一門編程語言的實現有哪些情況會導致它無法支持遞歸？
我實現過一門語言，由於一些特殊原因，導致它採用了動態作用域，但是這也能支持遞歸啊。我們都知道詞法作用域是支持遞歸的。
我自己又仔細想了下，寫了一個回答，各位答主可以先參考一下，因為這個話題可以在很多角度下討論。

1. proof assistant 如 Coq，Agda 之類，不支持 general recursion，對「遞歸」的支持是有限的。

2. Algol 60 之前的時代，編程語言有「遞歸」並不是一件理所當然的事：How recursion got into programming: a tale of intrigue, betrayal, and advanced programming-language semantics

強規範的語言不會支持 general recurison，否則無法保證 normalizing

謝邀。

假設你說的遞歸指的是general recursion，也就是能讓你永不停機的那個。

那麼， $lambda_{ ightarrow}$ 就是不支持遞歸的（它是strongly normalizing的）。

General observations
Given the standard semantics, the simply typed lambda calculus is strongly normalizing: that is, well-typed terms always reduce to a value, i.e., a https://wikimedia.org/api/rest_v1/media/math/render/svg/b43d0ea3c9c025af1be9128e62a18fa74bedda2a abstraction.

-- Wikipedia "Simply Typed Lambda Calculus"

關於這一點的證明，參見TaPL第12章Normalization或隨便在Google上搜索，有論文有課件。

（@大笨蛋千里冰封這問題是你提的然後邀請我的？那我就直接針對你的回答中提到的東西進行回答了：

還沒實現函數等特性，只有一個全局變數表（也就是還沒做scoping，剛寫完Parser的時候），它就無法支持遞歸。

不確定你對「全局變數表」的定義是啥，如果指的是 $Gamma$ （binding context）的話，那麼Untyped Lambda Calculus就是這樣的，在UTLC的語義下，你是可以實現general recursion的。你只要用Y-combinator就好。

其實只要支持eval函數和讀取文件就好了，這樣可以讀取自身然後eval它，這也是遞歸的一種形式（我在剛寫完Lice的Parser的時候就這樣玩了一次這樣的「讀取自己這個文件」然後遞歸，很有意思）

能搞出general recursion的方法多了，主要看哪個更簡潔，更加適合語言。畢竟我們生活在一個什麼都能圖靈完備的宇宙中，Minecraft可以，PPT可以，甚至一堆細胞的抽象模型都可以，還有啥不可以的呢？

好像它首先得有「函數」或者「方法」或者「程序」的概念才行。

「程序」這個概念是平凡和直覺的，一旦你定義了某個語言，比如你聲稱：「Lice是一門編程語言」，那麼(+ 1 1)自然就是程序了。而關於函數的概念，其實圖靈機（及各大圖靈機模擬器語言……）具有與general recursion等價的計算能力，但是圖靈機中沒有函數（狀態轉移「函數」是針對該形式語言的metalanguage而言的，不是對圖靈機本身而言的）。

你還有啥問題接著在評論問好了。

（另，看來上次你還是沒看懂Lambda Calculus的Wikipedia詞條……

依稀記得Fortran是沒有調用棧噠。。。。。就是說，每個函數的局部變數有固定的地址存放，如果你這個函數沒有退出，然後又調用了一次，新的局部變數就把原來的覆蓋掉了。。。。。。

我也實現過一門動態作用域的解釋型語言，我在給學生們介紹的時候也會專門指出這門語言支持遞歸，不過這並不嚴格，比如：

function test()

test()

end

這時候是遞歸，但是如果這樣做…

define arr={test}

test=null

arr[0]()

這就不是遞歸了…會報錯的

嚴格來說，如果一個語言只有匿名函數，那就是不支持遞歸，比如C++里的Lambda，遞歸下試試？

標籤甚麼鬼。。

能定義變量和函數就可以了吧？

畢竟

fun f(): f()

也是個遞歸

GLSL這類的某些語言不支持，因為不是所有的硬體都支持遞歸。

我寫的語言就不支持遞歸咯

連函數都不支持

https://github.com/wangxiaozhi123/Nee

更新5：

支持遞歸不需要局部變數，也不需要選擇結構，畢竟

fun f() { f() }

也是遞歸啊

更新4：

我提到過一個我寫的「可以支持前面定義的函數和後面定義的函數互相調用」的名字叫Lice的語言，這個特性根據我目前的思考深度，只有動態作用域的語言才可以實現，詞法作用域是不行的。但是它的確是可行的，我在repl裡面實現了一對函數，分別是odd和even，判斷奇偶的，定義如下：

(def odd num (if (== 0 num) false (even (- num 1)))) (def even num (if (== 0 num) true (odd (- num 1))))

然後這是Repl（謝謝 @Glavo 小可愛幫我寫Repl）里的表現：

這個補充是用於打另外一個答主 @劉明全的臉的。他說，

如果你想驗證的話可以看這裡 =&> lice-lang/lice

Repl是互動式的，也就是說讀取一行代碼然後就輸出它的運行結果，雖然所謂的編譯型解釋型其實都是糊弄初學者的概念，但是在這裡，Lice語言是符合你說的「解釋型」的語言。

話說打臉就應該上重鎚，我要向叛逆者學習。如果他以「我看不懂Lisp」為理由反駁我，我就發篇文章把他掛出來。

更新3：

其實只要支持eval函數和讀取文件就好了，這樣可以讀取自身然後eval它，這也是遞歸的一種形式（我在剛寫完Lice的Parser的時候就這樣玩了一次這樣的「讀取自己這個文件」然後遞歸，很有意思）

更新2：

好像它首先得有「函數」或者「方法」或者「程序」的概念才行。

更新：

我又稍微想了一下，這個問題可以站在很多角度討論，比如你可以從位元組碼/彙編層次討論，可以從作用域層次討論，等等。這些都接受，都是歡迎的。

原文：

我稍微想了一下，似乎只要一門語言沒有「局部變數」的概念就不能支持遞歸，在我剛開始實現那個語言的時候，還沒實現函數等特性，只有一個全局變數表（也就是還沒做scoping，剛寫完Parser的時候），它就無法支持遞歸。

也就是說只要有局部變數就可以支持遞歸了？但是我不知道咋證明。

歡迎知友評論區/回答區討論。

道理我都懂...可是為什麼會出現在偽娘話題和女裝少年話題里

a = a + 1

單純的SQL應該不能遞歸吧，store procedure不算。

cuda

竊以為，沒有相同或類似於「如果A，那麼做（任意指定的）B」的構造的編程語言將不會支持遞歸。

我當初剛學編程的時候，是一種basic語言，現在想不起來是哪一版了，但是記得它是：

解釋型程序。

什麼意思呢，就是像一篇文章一樣，從第一行開始，一行一行的解釋（執行），可以跳轉到文章的其他地方，也可以循環，但是沒有函數，自然也就不可能有遞歸。

據說「程序」這個名字就來自於「把過程按照順序執行」。

你可以想像你的程序只有唯一一個主方法，沒有別的方法（函數）的樣子，大概就是那種感覺。

後來程序發展出了新的類型：

編譯型程序。

就靈活多了，都可以遞歸，現在的程序大部分都是編譯型。但是當初剛出能遞歸的程序時，是很牛的突破。