C Programming
Functions
Recursion
Recursive Functions
Fibonacci Numbers
1
1
Growth is exponential: possible to
find r > 1 st. fn ≥ rn−2 .
√
2 Let r = 1+2 5
= 1.62, so that
r2 = r + 1
3 We need to prove that fn ≥ rn−2 .
R. K. Ghosh (IIT-Kanpur) C Programming February 24, 2011 6/7
C Programming
Functions
Recursion
Recursive Functions
Fibonacci Numbers
Basis: P (1) is true, f1 = 1, since r1−2 = r−1 ≤ 1.
Note, also that as r2−2 = 1 = f2 , P (2) holds.
Induction hypothesis: for a fixed n > 2, P (1), P (2) . . . P (n) are all
true.
Induction step: consider fn+1 = fn−1 + fn−2 .
Using hypothesis fn ≤ rn−2 + rn−3
So, fn ≤ rn−3 (r + 1) = rn−3 .r2 = rn−1 .
Hence P (n + 1) is true.
R. K. Ghosh (IIT-Kanpur) C Programming February 24, 2011 6/7
C Programming
Functions
Recursion
Examples of Recursive Functions
Fibonacci Function
#i n c l u d e < s t d i o . h>
int fib ( int n) {
i f ( n == 1 ) r e t u r n 1 ;
i f ( n == 2 ) r e t u r n 1 ;
r e t u r n f i b ( n−1) + f i b ( n −2);
}
i n t main ( ) {
int n;
p r i n t f (” Enter n : ” ) ;
s c a n f ( ”%d” , &n ) ;
p r i n t f ( ”%d t h f i b o n a c c i number = %d \ ” , n , fib (n ));
}
R. K. Ghosh (IIT-Kanpur) C Programming February 24, 2011 7/7
C Programming
Functions
Recursion
Examples of Recursive Functions
Fibonacci Function
fib(5)
fib(4) fib(3)
fib(3) fib(2) fib(2) fib(1)
fib(2) fib(1)
R. K. Ghosh (IIT-Kanpur) C Programming February 24, 2011 7/7
C Programming
Functions
Recursion
Examples of Recursive Functions
Efficient Computation of Fibonacci
To make it more efficient the strategy would be
Keep track of both current and previous fibonacci numbers
How many are to be computed?
Initially f (1) and f (2) are known and n − 2 other numbers to be
computed.
(
1, if n <= 2
fibo(cur, prev, n) =
fibo(cur+prev, cur, n-1)
So if n = 6 then 4 values are to be computed.
R. K. Ghosh (IIT-Kanpur) C Programming February 24, 2011 7/7
C Programming
Functions
Recursion
Examples of Recursive Functions
Efficient Computation of Fibonacci
#i n c l u d e < s t d i o . h>
i n t f i b o ( i n t cur , i n t prev , i n t n ) {
i f ( n−2 <= 0 )
return cur ;
r e t u r n f i b o ( c u r + p r e v , c u r , n −1);
}
i n t main ( ) {
int n;
p r i n t f ( ” E n t e r a +v e n : ” ) ;
s c a n f ( ”%d” , &n ) ;
p r i n t f ( ” f i b (%d ) = %d\n” , n , f i b o ( 1 , 1 , n ) ) ;
}
R. K. Ghosh (IIT-Kanpur) C Programming February 24, 2011 7/7
C Programming
Functions
Recursion
Examples of Recursive Functions
Fibonacci Function
from main
fibo(1, 1, 5) 5
5 return
return fibo(2, 1, 4)
5
return fibo(3, 2, 3)
5
return fibo(5, 3, 2)
R. K. Ghosh (IIT-Kanpur) C Programming February 24, 2011 7/7
C Programming
Functions
Recursion
Examples of Recursive Functions
Power Function
Recursive specification of xn is as follow:
1, if n = 0
pow(x, n) = x ∗ square(pow(x, n/2)), if odd(n)
square(pow(x, n/2)), otherwise
R. K. Ghosh (IIT-Kanpur) C Programming February 24, 2011 7/7
C Programming
Functions
Recursion
Examples of Recursive Functions
Power Function
#i n c l u d e < s t d i o . h>
i n t power ( i n t x , i n t n ) {
int t ;
i f ( n == 0 )
return 1;
t = power ( x , n / 2 ) ;
i f ( n%2 != 0 )
return x ∗ t ∗ t ;
return t ∗ t ;
}
i n t main ( ) {
int n , x ;
p r i n t f ( ” E n t e r x and n : ” ) ;
s c a n f ( ”%d %d” , &x , &n ) ;
p r i n t f ( ” power(%d , %d ) = %d\n” , x , n , power ( x , n ) ) ;
}
R. K. Ghosh (IIT-Kanpur) C Programming February 24, 2011 7/7
