Fibonacci using Recursion

Apr 28, 2015 at 12:22am
Make a program that will determine the fibonacci at the desired position number using recursion. Example:

Enter the first Fibonacci number: 12
Enter the second Fibonacci number: 18
Enter the position of the desired Fibonacci number: 15
The Fibonacci number at position 15 is: 9582


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
 #include<iostream>
using namespace std;


int fibonacci(int first, int second, int position = 1)
{
	int counter = 0, n;
	if (counter <= position)
	{
		n = first + second;
		n = first;
		first = second;
		counter++;
		position++;
		return fibonacci(first, second, position);
	}
}

int main()
{
	int first, second, position, n, counter;

	cout << "Enter the first fibonacci number: ";
	cin >> first;
	cout << "Enter the second fibonacci number: ";
	cin >> second;
	cout << "Enter the position of the desired fibonacci: ";
	cin >> position;

	cout << "The fibonacci number at position " << position << " is: " << fibonacci(first, second, position);

	system("pause>0");
	return 0;
}
Apr 28, 2015 at 1:31am
I changed this part but it still breaks
1
2
3
4
5
6
7
8
if (counter <= position)
	{
		n = first + second;
		first = n;
		second = first;
		counter++;
		position++;
	}
Apr 28, 2015 at 1:38am
Trace the recursion(aka what does the function return in the base case?)
Apr 28, 2015 at 5:14am
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<iostream>
using namespace std;


int fibo(int first, int second, int position)
{
	int counter = 0, sum;
	while(counter < position-2)
	{
		sum = first + second;
		first = second;
		second=sum;
		counter++;
	}
	return sum;
}

int main()
{
	int first, second, position, n, counter;

	cout << "Enter the first fibonacci number: ";
	cin >> first;
	cout << "Enter the second fibonacci number: ";
	cin >> second;
	cout << "Enter the position of the desired fibonacci: ";
	cin >> position;

	cout << "The fibonacci number at position " << position << " is: " << fibo(first, second, position);

	system("pause>0");
	return 0;
}


You have to use "while" loop instead of "if" loop if you want to repeat it a certain amount of time ie fibo is generated by summing the adjacent numbers again and again. Besides, return should be the value you want to cout ie the function can't return itself. Also, there are a little bit misconcepts. Look at my code.
Apr 28, 2015 at 9:46am
To Kyi's answer, that's not a recursive fibonacci. A recursive fibonacci DOES return itself. However that is indeed a correct iterative fibonacci.
Last edited on Apr 28, 2015 at 9:47am
Apr 28, 2015 at 2:43pm
A function is recursive if it calls itself. This is how the recursion part should be:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int fibo(int first, int second, int position)
{
    if (position < 1)
        throw std::invalid_argument("No position exists before the first element in a sequence.\n");
    else if (position == 1)
        //stuff
    else if (position == 2)
        //stuff
    else
    {
        //stuff
        return fibo(first, second, position - 1);
    }
}

Please don't tell me you can't figure out the rest from here.
Topic archived. No new replies allowed.