Рекурсивный алгоритм для суммы целых чисел нечетного числа

Question

Я выражаю алгоритмы в псевдокоде. Мне просто интересно, работает ли мой проект так же, как и оригинальный, показанный ниже. Предполагается, что алгоритм вычисляет сумму n нечетных натуральных чисел.

Это как алгоритм должен выглядеть:

procedure sumofodds(n:positive integer) 
    if n = 1 
     return 1 
    else 
     return sumofodds(n-1) + (2n-1) 

Это, как я разработал свой алгоритм:

procedure odd(n: positive integer) 
    if n = 1 
     return 1 
    if n % 2 > 0 
     return n + odd(n-1) // this means n is odd 
    if n % 2 = 0 
     return 0 + odd(n-1) // this means its even 

Answer 1

Одно небольшое улучшение, что мощь помощь определяя его с хвостом рекурсии. Рекурсия хвоста происходит, когда последнее, что нужно выполнить, - это рекурсивный вызов. Чтобы сделать этот хвост рекурсивным, используйте вспомогательный метод и передайте текущую сумму в качестве параметра. Я уверен, что псевдокод ниже хвост рекурсивный, поскольку, независимо от результата проверки (если нечетно), последний шаг - это рекурсивный вызов (математика происходит до рекурсивного вызова).

procedure SumOdds(n) 
    return SumOddsHelper(n, 0) 

procedure SumOddsHelper(n, sum) 
    if n = 1 return 1 

    if n is odd return SumOddsHelper(n-1, sum + n) 
    else return SumOddsHelper(n-1, sum) 

Answer 2

Ваш алгоритм не совпадает с оригиналом.

Оригинал вычисляет сумму первых n нечетных чисел.

Ваш алгоритм вычисляет сумму всех нечетных чисел в диапазоне 1..n.

Итак, для ввода n = 3 первый алгоритм будет вычислять 1 + 3 + 5, а ваш алгоритм будет вычислять 1 + 3.

(Если вы хотите более быстрый путь, то формула п * п вычисляет сумму первых п нечетных чисел)

Answer 3

Позвольте мне предложить вам реализовать вашу идею в Python. Вы можете быть удивлены, увидев, что рабочий код очень похож на псевдокод.

Это оригинальный алгоритм:

def sum_of_n_odds(n): 
    if n == 1: 
    return 1 
    else: 
    return sum_of_n_odds(n-1) + (2*n-1) 

И это одна Вы писали:

def sum_of_odds_up_to_n(n): 
    if n == 1: 
    return 1 
    if n % 2 > 0: # this means n is odd 
    return n + sum_of_odds_up_to_n(n-1) 
    if n % 2 == 0: # this means it's even 
    return 0 + sum_of_odds_up_to_n(n-1) 

Эти два алгоритма вычисления разные вещи. Вызов sum_of_n_odds(10) дает тот же результат, что и вызов sum_of_odds_up_to_n(19) или sum_of_odds_up_to_n(20). В общем случае sum_of_odds_up_to_n(n) эквивалентен sum_of_n_odds((n+1)//2), где // означает целочисленное деление.

Если вы заинтересованы в том, чтобы сделать вашу реализацию немного более эффективной, я предлагаю вам опустить окончательное условие if, где n % 2 == 0. Целое число либо нечетное, либо четное, поэтому, если оно не является нечетным, оно должно быть четным.

Вы можете получить другое усиление производительности, сделав рекурсивный вызов sum_of_odds_up_to(n-2), когда n является нечетным. В настоящее время вы тратите половину ваших вызовов функций на четные числа.

С помощью этих двух улучшений, код становится:

def sum_of_odds_up_to_n(n): 
    if n <= 0: 
    return 0 
    if n % 2 == 0: 
    return sum_of_odds_up_to_n(n-1) 
    return n + sum_of_odds_up_to_n(n-2) 

И это хвост рекурсивной версии:

def sum_of_odds_up_to_n(n, partial=0): 
    if n <= 0: 
    return partial 
    if n % 2 == 0: 
    return sum_of_odds_up_to_n(n-1, partial) 
    return sum_of_odds_up_to_n(n-2, partial+n) 

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

def sum_of_odds_up_to_n(n): 
    partial = 0 
    if n % 2 == 0: 
    n -= 1 
    while n > 0: 
    partial += n 
    n -= 2 
    return partial 

Самая быстрая реализация всех зависит от математического понимания. Рассмотрим сумму:

1 + 3 + 5 + ... + (n-4) + (n-2) + n 

Заметим, что вы можете соединить первый элемент с последним элементом, второй элемент со второй последний элемент, третий элемент с третьим последним элементом, и так далее:

(1 + n) + (3 + n-2) + (5 + n-4) + ... 

легко видеть, что это равно:

(n + 1) + (n + 1) + (n + 1) + ... 

Сколько терминов (n + 1) есть? Поскольку мы соединяем два слагаемых за один раз от исходной последовательности, в последовательности (n + 1) имеется половина числа.

Вы можете проверить сами, что в исходной последовательности (n + 1)/2. (Подсказка: посмотрите, что вы получите, если добавить 1 к каждому члену.)

Новая последовательность имеет в два раза меньше терминов или (n + 1)/4. И каждый член последовательности является (n + 1), поэтому сумма всей последовательности:

(n + 1) * (n + 1)/4 

В результате программа Python заключается в следующем:

def sum_of_odds_up_to_n(n): 
    if n <= 0: 
    return 0 
    if n % 2 == 0: 
    n -= 1 
    return (n+1)*(n+1)//4