在我的练习中，我必须决定函数是什么类型的递归。
我们必须从线性递归、尾递归和保护递归中进行选择，但我不太明白后两者之间的区别。
有人可以解释一下保护递归和尾递归之间的区别吗？
我们要区分的功能供参考：
pow2 0 = 1
pow2 n = 2 * pow2 (n-1)
factAux r i n
| i <= n = factAux (i * r) (i + 1) n | otherwise = r
factorial = factAux 1 1
init [x] = []
init (x:xs) = x : init xs
binom n 0 = 1
binom n k
| n == k = 1
| otherwise = binom (n - 1) k + binom (n - 1) (k …s我正在考虑在字符处分割字符串的问题c。
这表示为
break (c ==) s
其中 Haskell 库的定义break (c ==)足够接近
br [] = ([],[])
br s@(h:t) = if (c == h)
then ([],s)
else let (h',t') = br t in (h:h',t')
（假设我立即想要访问返回值的第二项，以便强制执行任何惰性求值。） 的递归调用似乎存储br t在h调用堆栈上，但该算法的一般意义表明：这应该是没有必要的。这是在常量堆栈空间中使用具有可变性的伪代码语言执行此操作的一种方法，其中 & 表示通过引用进行传递，列表以 LISPy 对的形式实现：
br(c,s) =
allocate res_head,res_rest
iter(c,s,&res_head,&res_rest)
return (res_head,res_rest)
iter(c,s,&res_head,&res_rest) =
case s of
[] -> set res_head = res_rest = [] -- and terminate
c:ss -> set res_head = [], res_rest = s …我在阅读《Joy of Kotlin》一书时遇到了这个有趣的问题。在第 4 章中，在解释尾递归时，作者提供了一个将两个数字相加的实现，如下所示。
tailrec fun add(a: Int, b: Int): Int = if (b == 0) a else add(inc(a), dec(b))
# where
fun inc(n: Int) = n + 1
fun dec(n: Int) = n - 1
这个函数的有趣之处在于返回 0，但如果删除add(3, -3)关键字，则会陷入 stackoverflow 。tailrec当程序看起来不完整时，它如何返回正确的答案。
我反编译了java字节码，看看尾部调用消除是如何完成的，这就是我所看到的。
public static final int add(int a, int b) {
while(b != 0) {
a = inc(a);
b = dec(b);
}
return a;
}
如果我在心里演练代码，循环或之前的递归调用应该导致无限循环，因为变量 b 永远不会变为零，因为起始值本身是负数。但是，运行上述 kotlin 代码或 java 代码会提供正确的结果。当使用调试器运行时，相同的代码会进入无限循环，正如我在心理演练中所期望的那样。这段代码如何在运行时给出正确的结果，但在调试模式下陷入无限循环？
我个人认为正确的实现应该如下所示，但我无法推理为什么第一个是正确的。
tailrec fun …#include<stdio.h>
int main()
{
static int x;
if(x == 10)
printf("\n thanks...");
x++;
return (x=main());
}
在运行程序时,它会卡在输出上:
谢谢...
这里有什么问题？
我尝试做一个尾递归函数,它将计算列表的元素,遵循规则,使用一个累加器,但当我像这样运行它:
lstcountr [1..98765432];;
我明白了:
System.OutOfMemoryException:抛出了类型'System.OutOfMemoryException'的异常.
这是我的函数(我认为是尾递归/高效):
let lstcountr ls =
let rec loop ls total =
match ls with
| [] -> total
| hd::tl -> loop tl total+1I
loop ls 0I
这可以做得更好吗？
我有一个索引纺织品的递归函数,如果我将它用于大型文本文件,我会得到一个堆栈空间溢出.我想因为我将递归部分放在let部分中我可以避免这个堆栈空间溢出,但我仍然得到它.使用此函数避免堆栈空间溢出的最佳方法是什么？
--lines to Map
parseLinesToWordEntryMap :: Int -> [String] -> M.Map Word [TextLocation] -> (M.Map Word [TextLocation])
parseLinesToWordEntryMap lineNumber [] wordEntryMap = wordEntryMap
parseLinesToWordEntryMap lineNumber (x:xs) wordEntryMap =
let
lineNumber' = lineNumber-1
wordEntryMapRec = parseLinesToWordEntryMap lineNumber' xs wordEntryMap
in
parseLineToWordEntryMap lineNumber x wordEntryMapRec
在球拍中,我定义了以下函数,我想知道它是否是尾递归的:
(define foo
(? (c m s1 s2)
(if (< c m)
(if (= (modulo m c) 0)
(foo (+ c 1) m (+ s1 c) s2)
(foo (+ c 2) m s1 (+ s2 c)))
(cons s1 s2))))
我的问题几乎就是这样,但我必须写一些其他内容来满足我的帖子质量标准.实际上,我不知道我的帖子质量标准是什么.
我在Programming Interviews Exposed(第3版)中阅读了有关递归的内容,其中它们呈现以下递归factorial函数:
int factorial(int n){
if (n > 1) { /* Recursive case */
return factorial(n-1) * n;
} else { /* Base case */
return 1;
}
}
在同一页面的底部(第108页),他们讨论了尾递归函数:
请注意,当递归调用返回的值本身立即返回时,如前面的定义所示
factorial,该函数是尾递归的.
但这是真的吗？函数中的最后一个调用是*调用,因此不会保留此堆栈帧(如果我们不考虑编译器优化)？这真的是尾递归吗？
嗨我在理解尾递归方面有些困难.我知道避免无限循环以及内存使用非常重要.我在"F#中的专家"中看到了一些关于像Fibonacci这样的简单函数的例子,但是当我的结果不仅仅是一个数字时,我认为我没有看过代码.
那么累加器会是什么？我不确定...
这是我写的一个递归函数.它使用快速排序算法计算数组中的反转次数.[它取自斯坦福大学的Coursera MOOC Algo I的练习]
如果有人能解释如何使尾部递归,我将不胜感激.[另外,我已经从命令式代码翻译了那段代码,因为我之前在R中写过,所以风格根本不起作用......]
另一个问题:语法是否正确,A是一个(可变)数组,我let A = ....到处都写过？为A <- ....更好地/一样的吗？
open System.IO
open System
let X = [|57; 97; 17; 31; 54; 98; 87; 27; 89; 81; 18; 70; 3; 34; 63; 100; 46; 30; 99;
10; 33; 65; 96; 38; 48; 80; 95; 6; 16; 19; 56; 61; 1; 47; 12; 73; 49; 41;
37; 40; 59; 67; 93; 26; 75; 44; 58; 66; 8; 55; 94; 74; 83; 7; 15; 86; …我有一个疑问,我必须为这个pow函数做一个尾递归:
pow(_, 0) -> 1;
pow(N, X) when X > 0 -> N * pow(N, X - 1).
我已经读过它了,但是我还没有完全理解它,有人可以解释我如何在尾递归中使用这个函数吗？