Является ли эта программа рекурсивной?

Мы с другом обсуждали, был ли алгоритм, который мы должны были анализировать для домашней работы, был рекурсивным или нет, но он настаивает на том, что это так. Таким образом, алгоритм выглядит следующим образом:Является ли эта программа рекурсивной?

SomeAlgo(x) 
{ 
    x--; 

    if (x > 1) 
    { 
     SomeAlgo(x); 
    } 
    else 
    { 
     return x; 
    } 
}

Я сказал ему, что это не хвостовая рекурсия, потому что SomeAlgo (х) не последнее утверждение будет выполняться. Нам нужен базовый случай, но мы этого не делаем. Если бы у нас был базовый случай, первый код, который будет выполняться, будет первым, и вызов к нему (который возвращает возвращаемое значение) будет последним.

Если это не рекурсивный хвост, можете ли вы сказать мне, что нужно сделать, чтобы сделать его хвостовым рекурсивным?

источник

2013-05-19 George White

Какой язык программирования это? Вы получите больше просмотров, если вы укажете язык программирования, который вы используете в тегах. –

SomeAlgo (х) является последнее утверждение будет выполнено, если X больше 1.

источник

2013-05-19 15:42:45

Я думал, что вам нужно иметь возвратный алго (x), чтобы иметь хвостовой рекурсивный алгоритм. Последним оператором, который выполняется, является return x, а не algo (x). Я ошибаюсь? –

Если единственный возможный способ использования хвостовой рекурсии - вернуть другой вызов самому себе, то всякая реализация «хвостовой рекурсии» приведет к бесконечной рекурсии и, следовательно, к stackoverflowerror, поскольку она никогда не сможет вернуть статический стоимость. В случае вашего алгоритма «return x;» где x <= 1 - ваш базовый регистр. – jonhopkins

Итак, еще один возврат x - это базовый регистр, верно? Но это не первый оператор, который выполняется, это последняя строка кода, которая выполняется, верно? –

Является ли эта программа рекурсивной?

ответ

Смежные вопросы