Essential Books

The basic idea of recursion

suggest change

What is recursion:

In general, recursion is when a function invokes itself, either directly or indirectly. For example: 

// This method calls itself "infinitely"
public void useless() {
    useless();  // method calls itself (directly)
}

Conditions for applying recursion to a problem:

There are two preconditions for using recursive functions to solving a specific problem:

  1. There must be a base condition for the problem, which will be the endpoint for the recursion. When a recursive function reaches the base condition, it makes no further (deeper) recursive calls.
  2. Each level of recursion should be attempting a smaller problem. The recursive function thus divides the problem into smaller and smaller parts. Assuming that the problem is finite, this will ensure that the recursion terminates.

In Java there is a third precondition: it should not be necessary to recurse too deeply to solve the problem; see http://stackoverflow.com/documentation/java/914/recursion/15048/deep-recursion-is-problematic-in-java

Example

The following function calculates factorials using recursion. Notice how the method factorial calls itself within the function. Each time it calls itself, it reduces the parameter n by 1. When n reaches 1 (the base condition) the function will recurse no deeper. 

public int factorial(int n) {
    if (n <= 1) { // the base condition 
        return 1;
    } else {
        return n * factorial(n - 1);
    }
}

This is not a practical way of computing factorials in Java, since it does not take account of integer overflow, or call stack overflow (i.e. StackOverflowError exceptions) for large values of n.

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