Рекурсивная функция для вычисления суммы всех чисел от 1 до n?

Question

Проблема, которую я пытаюсь решить:

Write a Scheme function called "my-sum" which takes a 
nonnegative number n and outputs the value 
1+2+ .. +n 
Your solution should use recursion. 

У меня есть общая функция, определенная ... и я знаю, как я хотел бы сделать это в C++ без рекурсии. Но мне сложно решить, как это сделать с помощью Схемы.

То, что я получил до сих пор:

(define my-sum 
(lambda (x) 
    (+ x (- x 1)))) 

Answer 1

Вот чисто рекурсивное решение:

(define (my-sum x) 
    (if (zero? x) 
     0 
     (+ x (my-sum (- x 1))))) 

К сожалению, это не хвостовая рекурсия. Вот версия, которая является хвостовой рекурсией:

(define (my-sum x sum) 
    (if (zero? x) 
     sum 
     (my-sum (- x 1) (+ x sum)))) 

Вы можете назвать это так:

(my-sum x 0) 

Здесь sum является аккумулятор.

Ваш второй ответ делает то же самое, используя внутреннюю вспомогательную функцию, которая является хвостовой рекурсивной, предоставляя начальное значение аккумулятору при первоначальном вызове внутренней вспомогательной функции.

Answer 2

(define (my-sum n) 
    (define (my-sum-helper n m) 
    (if (= 0 n) 
     m 
     (my-sum-helper (- n 1) (+ n m)))) 
    (my-sum-helper n 0)) 

Answer 3

Можно также использовать "по имени давайте здесь легко понять функцию, которая определяет и сразу же применяет рекурсию:

(define (mysum n) 
    (let loop ((m 0) 
      (s 0)) 
    (cond 
     [(> m n) s] 
     [else (loop (add1 m) 
        (+ s m))]))) 

Ключевое слово«еще»может быть опущено. Код, использующий «if», также можно использовать здесь вместо «cond», поскольку есть только 2 условия.

Answer 4

Упражнение состоит в суммировании чисел от 1 до n с использованием рекурсивной функции.

Это упражнение из книги SICP. Решения для упражнений доступны из многих источников. В этом случае «Билл Ящерица» дает очень хорошее объяснение:

http://www.billthelizard.com/2010/04/sicp-exercise-130-iterative-sums.html

Заметьте, что в «реальной» Ракетка, можно было бы просто написать:

(for/sum ([x (in-range 1 (+ n 1))]) ; let x run through 1, 2, ... n 
    x)         ; add x to the running sum