Функции в С++ для начинающих. Рекурсия. Числа Фибоначчи

Опубликовано 06.04.2012 | Автор: admin

К сведению:

Ряд Фибоначчи: 0 1 1 2 3 5 8 13 21 …
Ряд Фибоначчи начинается с 0 и 1 и обладает тем свойством, что каждое последующее число Фибоначчи представляет собой сумму двух предыдущих.

Один из классических примеров рекурсии — программа, вычисляющая ряд Фибоначчи. В этой статье как раз показывается код программы, вычисляющей числа Фибоначчи.

Ряд Фибоначчи можно рекурсивно определить следующим образом:
fibonacci( 0 ) = 0
fibonacci( 1 ) = 1
fibonacci( n ) = fibonacci( n — 1 ) + fibonacci( n — 2 )

Пример кода:

#include <iostream>

using namespace std;

int fibo(int value){
    if (0 == value || 1 == value) return value;     
    else return fibo(value - 1) + fibo(value - 2);		//Рекурсивный вызов функции
}

int main(){
    for (int i=0; i<20; i++){
        cout << "fibonacci " << i << " ==> " << fibo(i) << '\n';	//нерекурсивный вызов fibo(i)
    }
	
	cin.ignore().get();
}

#include <iostream>

using namespace std;

int fibo(int value){

if (0 == value || 1 == value) return value;

else return fibo(value - 1) + fibo(value - 2); //Рекурсивный вызов функции

}

int main(){

for (int i=0; i<20; i++){

cout << "fibonacci " << i << " ==> " << fibo(i) << '\n'; //нерекурсивный вызов fibo(i)

}

cin.ignore().get();

}

Внутри main использован обычный цикл. Он используется для того, чтобы посмотреть числа Фибоначчи по нескольким значениям сразу. Первый вызов функции fibo(int) не считается рекурсивным (что на самом деле логично, ведь не fibo(int) вызвало fibo(int)). А дальше идут проверки и при необходимости новые вызовы. Внутри функции задействуются два результата вычислений, которые складываются между собой. При этом каждое из двух вычислений происходит рекурсивным образом.

ВНИМАНИЕ!

В отличие от обычных способов сложения, в показанном коде в качестве слагаемых используются вызовы функций.
Первым может сработать как вызов fibo(n — 1), так и вызов fibo(n-2). Ни в коем случае не полагайтесь на порядок выполнения (слева-направо или справа-налево) в таких случаях.

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

На заметку:

Слева-направо гарантировано только для четырёх операций: || && ?:. И это при условии, что эти операции применяются не к пользовательскому классу, а к фундаментальным типам данных.

У операции ?: первым всегда оценивается самый левый операнд; если результат его оценки ненулевой (истинный), то следующим оценивается средний операнд, а последний операнд игнорируется; если же результат оценки самого левого операнда равен нулю (ложный), то следующим оценивается третий операнд, а средний игнорируется.

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

Написание программ, которые предполагают определенный порядок оценки операндов операций, отличных от && || , ?:, может приводить к логическим ошибкам.

Программы, предполагающие определенный порядок оценки операндов операций, отличных от && || , ?:, могут работать по-разному на системах с различными компиляторами.

Вернёмся к коду. Смотрим на код, вспоминаем, что там такое написано. Поскольку мы используем, так сказать, двойную рекурсию, то каждый новый рекурсивный шаг удваивает число экземпляров функции в памяти. А это обозначает, что память очень быстро забивается. Число рекурсивных вызовов, необходимых для вычисления n-го числа Фибоначчи, оказывается порядка 2ⁿ. Объем работы нарастает слишком быстро. Вычисление только 20-го числа Фибоначчи требует порядка 2²⁰, или около миллиона вызовов, вычисление 30-го числа Фибоначчи требует порядка 2³⁰, или около миллиарда вызовов и т. д. В теории численных методов это называется экспоненциальной сложностью. Проблемы такого рода не под силу даже самым мощным компьютерам в мире! Вопросы сложности вообще, и экспоненциальной сложности в частности, детально рассматриваются в специальных курсах, обычно называемых "Алгоритмы".