fibonacci series

recursion

Source Code

//
//  Fibonacci.h
//  Algorithms
//
//  Created by intoxicated on 1/4/14.
//

#import <Foundation/Foundation.h>

@interface Fibonacci : NSObject

+ (id)initFibWith:(NSInteger)size;

- (void)resetWithSize:(NSInteger)size;

- (long)recursive:(NSInteger)nth;
- (long)memorization:(NSInteger)nth;
- (long)iter1:(NSInteger)nth;
- (long)iter2:(NSInteger)nth;

@end
//
//  Fibonacci.m
//  Algorithms
//
//  Created by intoxicated on 1/4/14.
//

#import "Fibonacci.h"

#define integer(x) [NSNumber numberWithLong:x]

static Fibonacci * instance;

@interface Fibonacci ()
@property (nonatomic, strong) NSMutableArray * array;
@end

@implementation Fibonacci

+ (id)initFibWith:(NSInteger)size
{
@synchronized(self)
{
if (instance == NULL){
instance = [[self alloc] init];
instance.array = [[NSMutableArray alloc] initWithCapacity:size+1];
for(int i = 0; i < size+1; i++)
}
}

return instance;
}

- (void)resetWithSize:(NSInteger)size
{
instance.array = [[NSMutableArray alloc] initWithCapacity:size+1];
for(int i = 0; i < size+1; i++)
}

/**
* Basic recursive Fibonnacci nth number
* O(n!)
*/
- (long)recursive:(NSInteger)nth
{
if(nth < 2)
return nth;
return [self recursive:nth-1] + [self recursive:nth-2];
}

/**
* Improved recursive Fibonacci by memorizing
* perform O(n) additions
*/
- (long)memorization:(NSInteger)nth
{
if(nth < 2)
return nth;
else
{
if([instance.array objectAtIndex:nth] == [NSNull null])
{
[instance.array insertObject:integer([self memorization:nth-1] + [self memorization:nth-2])
atIndex:nth];
}
return [[instance.array objectAtIndex:nth] integerValue];
}
}

/**
* Same as above but savin some space by using dynamic programming
* running O(n) space O(n)
*/
- (long)iter1:(NSInteger)nth
{
[instance.array replaceObjectAtIndex:0 withObject:integer(0)];
[instance.array replaceObjectAtIndex:1 withObject:integer(1)];

for(int i = 2; i <= nth; ++i)
{
[instance.array replaceObjectAtIndex:i withObject:
integer([[instance.array objectAtIndex:i-1] integerValue] +
[[instance.array objectAtIndex:i-2] integerValue])];
}
return [[instance.array objectAtIndex:nth] integerValue];
}

/**
* This one only requires to remember previous two number to get
* next fibonacci number
* running O(n) space O(1)
*/
- (long)iter2:(NSInteger)nth
{
NSInteger prev = 1;
NSInteger curr = 0;
NSInteger next;
for(int i = 1; i <= nth; i++)
{
next = curr + prev;
prev = curr;
curr = next;
}
return curr;
}

@end
//
//  main.m
//  Fibonacci
//
//  Created by intoxicated on 1/4/14.
//

#import <Foundation/Foundation.h>
#import "Fibonacci.h"

#define SIZE 15 //change this to see difference
//first recursive method would take much longer if size exceeds 45

#define RESET(obj) [obj resetWithSize:SIZE];

int main(int argc, const char * argv[])
{
@autoreleasepool {
Fibonacci * test = [Fibonacci initFibWith:SIZE];

NSDate *methodStart = [NSDate date];
NSLog(@"Recursive %d th Fibonacci: %lu", SIZE,[test recursive:SIZE]);
NSDate *methodFinish = [NSDate date];
NSTimeInterval executionTime = [methodFinish timeIntervalSinceDate:methodStart];
NSLog(@"Execution Time = %f", executionTime);

RESET(test);

methodStart = [NSDate date];
NSLog(@"Memorized Recursive %dth Fibonacci: %lu", SIZE, [test memorization:SIZE]);
methodFinish = [NSDate date];
executionTime = [methodFinish timeIntervalSinceDate:methodStart];
NSLog(@"Execution Time = %f", executionTime);

RESET(test);

methodStart = [NSDate date];
NSLog(@"Speed up more! %dth Fibonacci: %lu", SIZE, [test iter1:SIZE]);
methodFinish = [NSDate date];
executionTime = [methodFinish timeIntervalSinceDate:methodStart];
NSLog(@"Execution Time = %f", executionTime);

RESET(test);

methodStart = [NSDate date];
NSLog(@"FASTER! %dth Fibonacci: %lu", SIZE, [test iter2:SIZE]);
methodFinish = [NSDate date];
executionTime = [methodFinish timeIntervalSinceDate:methodStart];
NSLog(@"Execution Time = %f", executionTime);

}
return 0;
}