#include<iostream>
using namespace std;

/* Fibonacci number through recursion.
 * This function returns the "nth" Fibonacci number
 */
int Fibonacci(int n)
{
	if(n == 0)
		return 0;
	if(n== 1)
		return 1;
	return Fibonacci(n-1) + Fibonacci(n-2);
}

/* this can also be done without recursion
int nonRecursiveFibonacci(int n)
{
	int a=0,b=1,c;
	if(n ==0 )
		return a;

	if(n==1)
		return b;

	for(int i=2; i<=n; i++) //We start from 2, since 0 and 1 cases have been handled
	{
		c=a+b; //new term
		a=b;  	//move to next terms
		b=c;
	}

	return c;
}
*/

int main()
{
	int num;
	cout<<"Enter the index: ";
	cin>>num;

	cout<<"The "<<num<<"th Fibonacci number is: "<<Fibonacci(num)<<endl;

	return 0;
}