Maomao goes to work (recursive)

describe

Maomao finally succeeded in applying for the job after countless hardships , Work in a software company , But because the house he rented is far away , And his electric car is older , You need to recharge every time you ride a section of the road , Fortunately, the charging speed is relatively fast , He just had time to rush to work .

Between the company and the rented house M-2 A charging station , His electric car can ride 1 Station or 2 Distance of the station , Set the first 1 The station is a rented house , The first M The station is a company , And the battery was full at the beginning , How many ways can he go to the company ？

Input
Multiple sets of test data , Please use while(…) Read in the data , until EOF.

Each set of data contains an integer M（2<=M<=40）, Indicates the total number of stations .

Output
For each set of data , Please output the number of different charging methods .

sample input 1

2
3

sample output 1

1
2

#include<stdio.h>

int charge(int n){
    
	if(n==2) return 1;
	else if(n==3) return 2;
	else if(n>3){
    
		return charge(n-1)+charge(n-2);
	}
}

int main(){
    
	int m;
	while(scanf("%d",&m)!=EOF){
    
		printf("%d\n",charge(m));
	}
}