Essential Books

Computing the Nth Fibonacci Number

suggest change

The following method computes the Nth Fibonacci number using recursion. 

public int fib(final int n) {
    if (n > 2) {
        return fib(n - 2) + fib(n - 1);
    }
    return 1;
}

The method implements a base case (n <= 2) and a recursive case (n>2). This illustrates the use of recursion to compute a recursive relation.

However, while this example is illustrative, it is also inefficient: each single instance of the method will call the function itself twice, leading to an exponential growth in the number of times the function is called as N increases. The above function is O(2N), but an equivalent iterative solution has complexity O(N). In addition, there is a “closed form” expression that can be evaluated in O(N) floating-point multiplications.

Found a mistake? Have a question or improvement idea? Let me know.

Feedback about page:

Feedback:
Optional: your email if you want me to get back to you:

Recursion:
* Recursion
* The basic idea of recursion
* Deep recursion is problematic in Java
* Types of Recursion
* Computing the Nth Fibonacci Number
* Computing the Nth power of a number
* Traversing a Tree data structure with recursion
* StackOverflowError recursion to loop
* Reverse a string using Recursion
* Computing the sum of integers from 1 to N
Table Of Contents
0 Inheritance
1 Getting started with Java
2 Streams
3 Exceptions
4 Collections
5 Lambda Expressions
6 Generics
7 File I/O
8 Arrays
9 Interfaces
10 Maps
11 Strings
12 InputStreams and OutputStreams
13 Default Methods
14 Classes and Objects
15 Basic Control structures
16 Concurrent Programming Threads
17 Console I/O
18 Singletons
19 Visibility controlling access to members of a class
20 Regular Expressions
21 Autoboxing
22 Documenting Java Code
23 Executor, ExecutorService and Thread pools
24 Object Class Methods and Constructor
25 JAXB
26 Primitive Data Types
27 Networking
28 Optional
29 Enums
30 HttpURLConnection
31 Annotations
32 Audio
33 Data Class
34 Calendar and its Subclasses
35 Nashorn JavaScript engine
36 Java Native Interface (JNI)
37 Remote Method Invocation (RMI)
38 Iterator and Iterable
39 Operators
40 Asserting
41 Scanner
42 Properties Class
43 Preferences
44 Reflection API
45 Constructors
46 ByteBuffer
47 Serialization
48 JSON in Java
49 Random Number Generation
50 Recursion
51 Polymorphism
52 StringBuilder
53 Refernce Data Types
54 Bit Manipulation
55 Java Agents
56 Encapsulation
57 Type Conversion
58 BigInteger
59 BigDecimal
60 RSA Encryption
61 Varargs Variable Arguments
62 ThreadLocal
63 Logging
64 static keyword
65 Disassembling and Decompling
66 Resources on classpath
67 log4j, log4j2
68 JVM Flags
69 Oracle Official Code Standard
70 Character encoding
71 Java Memory Management
72 Immutable Objects
73 Object Cloning
74 Alternative Collections
75 Lists
76 BufferedWriter
77 LocalTime
78 Sets
79 Comparable and Comparator
80 JVM Tool Interface
81 Nested and Inner Classes
82 Apache Commons Lang
83 Getters and Setter
84 The Classpath
85 Bytecode Modification
86 XML Parsing using JAXP
87 Reference Types
88 Localization and Internationalization
89 JAX-WS
90 XML XPath Evaluation
91 Performance Tuning
92 Parallel programming with ForkJoin framework
93 Common Pitfalls
94 Non-Access Modifiers
95 Java Compiler
96 XJC
97 Installing Java Standard Edition
98 Process
99 Command line argument processing
100 Dates and Time using java.time
101 Fluent Interface
102 XOM - XML Object Model
103 Just in Time JIT compiler
104 FTP File Transfer Protocol
105 Java Native Access JNI
106 Modules
107 Pitfalls - exceptions
108 Pitfalls - language syntax
109 ServiceLoader
110 ClasssLoader
111 Object References
112 Pitfalss - performance
113 Creating Images Programmatically
114 Applets
115 NIO Networking
116 New File I/O
117 Secure objects
118 Pitfalls - threads and concurrency
119 Splitting a string into fixed length parts
120 Pitfalls - nulls and NullPointerException
121 SecurityManager
122 JNDI
123 super keyword
124 java.util.Objects class
125 Java command: java and javaw
126 Atomic types
127 Floating Point Operations
128 Converting to and from strings
129 sun.misc.Unsafe
130 Java Memory Model
131 Java deployment
132 Java plugin system implementations
133 Queues and deques
134 Runtime commands
135 NumberFormat
136 Security and Cryptograhy
137 Java Virtual Machine JVM
138 Unit Testing
139 JavaBean
140 Expressions
141 Literals
142 Java SE 8 Features
143 Java SE 7 Features
144 Packages
145 Concurrency and Money
146 Concurrent Collections
147 Using ThreadPoolExecutor in multi-threaded applications
148 Java Editions, versions, releases and distributions
149 Dynamic method dispatch
150 JMX
151 Security and cryptography
152 Generating Java Code
153 JShell
154 Benchmarks
155 Collection Factory Methods
156 Multi-release JAR files
157 Stack-Walking API
158 TreeMap and TreeSet
159 Sockets
160 Java Sockets
161 Using other scripting languages in Java
162 Functional interfaces
163 List vs. set
164 2D graphics
165 Reflection
166 Deque interface
167 Enum Map
168 EnumSet class
169 Local Inner class
170 Java Print Service
171 Immutable class
172 String Tokenizer
173 File upload to S3 / AWS
174 Readers and writers
175 Hashtable
176 Enum starting with a number
177 SortedMap
178 WeakHashMap
179 LinkedHashMap
180 StringBuffer
181 Choosing Collections
182 C++ Comparison
183 CompletableFuture
184 Contributors