32 votes 32 votes Consider the following recursive definition of $fib$: fib(n) := if n = 0 then 1 else if n = 1 then 1 else fib(n-1) + fib(n-2) The number of times $fib$ is called (including the first call) for evaluation of $fib(7)$ is___________. Programming in C gate1991 programming recursion normal numerical-answers + – Kathleen asked Sep 12, 2014 • retagged Apr 17, 2021 by Lakshman Bhaiya Kathleen 10.2k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
4 votes 4 votes Formula for no.of calls in f(n) =2f(n)-1 when f(0)=1 only applied fibonacci series where f(0)=1 f(1)=1 f(2)=2 i,e (f(0)+f(1)) f(3)=3............f(7)=21 so no.of calls 2(21)-1=41 remember when f(0)=0,f(1)=1 then formula changes as 2f(n+1)-1 supraja answered Apr 28, 2015 supraja comment Share Follow See 1 comment See all 1 1 comment reply minal commented Aug 22, 2015 reply Follow Share how no of call is 2f(n)-1 ?? 2 votes 2 votes Please log in or register to add a comment.
3 votes 3 votes #include <stdio.h> int fib(int n); int count =0 ; int main() { fib(7); printf("%d" , count); return 0; } int fib(int n) { count++; if (n==0) return 1; else if (n==1) return 1; else return (fib(n-1) + fib(n-2)); } mehul vaidya answered Jul 21, 2018 mehul vaidya comment Share Follow See all 0 reply Please log in or register to add a comment.
1 votes 1 votes For those who are having difficulty visualising the 41 functions calls for fib(7), I have drawn the recursion tree. Ashmita answered Mar 18, 2021 Ashmita comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes total 41 calls Prashant bhardwaj answered Jul 19, 2023 Prashant bhardwaj comment Share Follow See all 0 reply Please log in or register to add a comment.