递归函数返回sum，努力理解为什么？

下面的功能是给我一个审查表：递归函数返回sum，努力理解为什么？

(define mystery(lambda(m n) 
       (cond 
        ((= m 0) n) 
        ((= n 0) m) 
        (#t (+ 2(mystery(- m 1)(- n 1)))) 
        )))

前两个条件简单，它只是递归otherwise是交代不清的我。在我看来，递归将继续，直到它们都等于零，这当然不会返回总和。有人可以提供解释吗？

来源

2017-03-06 bgb102

我觉得最好的方法不是嵌套而是预先计算。综观我们与零个测试基础案例：

(mystery 0 2) ; ==> 2 
(nystery 3 0) ; ==> 3

因此，每一个的至少一个参数是零时间则返回其他参数。让我们试着用非零值，记得你看，我们已经做了值的第二之前，你只是它的结果打开它：

(mystery 1 3)  ; == 
(+ 2 (mystery 0 2)) ; == (we switch known value) 
(+ 2 2)       
; ==> 4 

(mystery 4 1)  ; == (we substitute with the expression) 
(+ 2 (mystery 3 0)) ; == (we switch known value) 
(+ 2 3) 
; ==> 5

因为我们知道基本情况总是返回我们没有其他的价值需要预先计算。下面是这样做的：

(mystery 3 9)     ; == (we substitute with the expression) 
(+ 2 (mystery 2 8)    ; == (we substitute with the expression) 
(+ 2 (+ 2 (mystery 1 7)))  ; == (we substitute with the expression) 
(+ 2 (+ 2 (+ 2 (mystery 0 6))) ; == (we substitute with the expression, n, which is 6) 
(+ 2 (+ 2 (+ 2 6)))   ; == (we substitute (+ 2 6)) 
(+ 2 (+ 2 8))     ; == (we substitute (+ 2 8)) 
(+ 2 10)      ; == (we substitute (+ 2 10) 
; ==> 12

我们可以概括会发生什么。 n和m的最低值将决定递归何时结束。在每一步它会加2和递归。因此，它是制作一个奇特的方式：

(define (double-min n m) 
(let ((vmin (min n m)) 
     (vmax (max n m))) 
    (+ (* 2 vmin) (- vmax vmin))))

这又是因为如果n > m添加两个数字，然后2*m+(n-m) = m+m+(n-m) = m+n

来源

2017-03-06 19:31:05 Sylwester

非常感谢，让它更清晰 – bgb102

这个答案是错误的，很难遵循。 '（神秘0 ）'应该是''，而不是'0'。 “神秘”实现了另外的问题标题暗示，而不是“双分”。 – jerry

@jerry与OPs代码一样，Mystery不**执行加法操作。如果'n'或'm'为零，则结果为零。默认情况下，将两个参数减1后的递归结果相加。因此，基本情况是当两者中的最小者为零时，使函数计算它的最小参数的两倍。因此'（* 2（min n m））'。使用预先计算的值来替代是推断纯递归函数的最简单方法。 – Sylwester

首先，让我们来格式化代码好一点，看看发生了什么：

(define (mystery m n) 
    (cond ((= m 0) n) 
     ((= n 0) m) 
     (else (+ 2 (mystery (- m 1) (- n 1))))))

现在，请记住，一个cond只执行对应于作为true（从上到下）的第一个条件的动作，其他人被忽略。如果没有条件是true，则执行else零件。重要的是要记住只有一个动作被执行。

特别是，你mystery程序将停止时要么m或n变为零，而不是当都变为零。当其中一个达到零时，递归开始放松，返回总和。跟踪执行时，你可以看到这一点 - 例如，在球拍：

(require racket/trace) 
(trace mystery) 
(mystery 3 2) 

>(mystery 3 2) 
> (mystery 2 1) 
> >(mystery 1 0) 
< <1 
< 3 
<5

来源

2017-03-06 16:44:46

只是为了奥斯卡·洛佩斯的回答阐述（我不能在评论中格式化此）：我发现，它的经常有用写这些各种各样的小递归数学函数向下如同它们是数学：

设m和n是自然数，然后

N + M = N如果m = 0;
如果n = 0，则n + m = m;
n + m = n-1 + m-1 + 2;
没有其他情况。

来源

2017-03-06 17:17:13 tfb

(define mystery(lambda(m n) 
       (cond 
        ((= m 0) n) 
        ((= n 0) m) 
        (#t (+ 2 (mystery (- m 1) (- n 1)))) 
        )))

第一和第二条件是显而易见的奇特的方式。

第三语句是如何工作的说明：

1中的每个被取出的m和n及保持为2该功能之外。这继续直到或者m是0或n是0。

来源

2017-03-07 11:37:46 rnso

第一2箱子是显而易见的，2号，其中号码之一是0的总和，等于所述其他号码。

在最后一种情况下，在检查参数为0之后，我们确定它们都是非0。假设该神秘返回它的2个参数的总和，然后

(+ 2 (mystery (- arg1 1) (- arg2 1)))

将返回一个总和等于(mystery arg1 arg2)并最终停止时的参数中的一个是0，返回所希望的结果。

假设神秘回报其2个参数的总和在这里是关键，并称为递归信仰的飞跃。（Google it）

来源

2017-03-08 12:37:26

递归函数返回sum，努力理解为什么？

回答

相关问题