Занятие 8. Функции и рекурсия

Задача «Числа Фибоначчи»

Условие

Напишите функцию fib(n), которая по данному целому неотрицательному n возвращает n-e число Фибоначчи. В этой задаче нельзя использовать циклы — используйте рекурсию.

Тесты

Входные данные Правильный ответ Что вывела программа Результат 
6
 
8
 

				
			

			
			

				
				
1


				
1

				

				
			

			
			

				
				
2


				
1

				

				
			

			
			

				
				
3


				
2

				

				
			

			
			

				
				
4


				
3

				

				
			

			
			

				
				
5


				
5

				

				
			

			
			

				
				
7


				
13

				

				
			

			
			

				
				
8


				
21

				

				
			

			
		
	

	




  
Нужна подсказка?

  
  

    Подсказка 1
    
Рекурсивно вычисляем числа Фибоначчи без циклов.

    
  

  
  

    Подсказка 2
    
Базовые случаи: F(0)=0, F(1)=1.