Рекурсивная функция C++

Question

Я пытаюсь создать рекурсивную функцию следующим образом.

Функция принимает счетчик k и до тех пор, что счетчик больше нуля, я хотел бы назвать это рекурсивно, так что в конце концов, я в конечном итоге с чем-то вроде этого:

result = 2(2(2n+1)+1)+1 

где последний n (когда k = 0) должно быть равным нулю.

int pass(int k, int n) 
{ 
    if(k==0) 
    { 
     n = 0; 
    } 
    else 
    { 
     k--; 
     return pass(k, 2*n+1); 
    } 
} 

Может ли кто-нибудь дать мне подсказку о том, как это сделать?

Answer 1

Изменить

n = 0; 

Для

return n; 

Чтобы вернуть результат.

Остальная часть кода в порядке

Answer 2

В настоящее время поведение вашего кода undefined, поскольку вы явно не возвращаете значение на всех путях управления.

Ваш код может упростить до:

int pass(int k, int n) 
{ 
    return k ? 2 * pass(k - 1, n) + 1 : 1; 
} 

Здесь я использовал трехкомпонентную условный оператор. 2 * pass(k - 1, n) + 1 возвращается, если k отличен от нуля, 1 возвращается в противном случае.

В этом случае не следует переполнять int. Обратите внимание, что максимальный размер int может быть как 32767. Вместо этого используйте вместо этого тип long.

Также обратите внимание, что рекурсия обычно не является хорошим способом решения проблем типа O (n); вы можете получить ошибки во время выполнения из-за превышения лимита стека функции вызова: вместо этого сверните с петлей.