the very first example about recursion is finding the factorial of a number which is brain-deadly simple:
int factorial(int n) {
if(n < 1) return 1;
return n * factorial(n-1);
}
this is a quite bad example since it runs on o(n) time, and takes o(n) space. the process for computing 5! is;
factorial(5)
(5 * (factorial 4))
(5 * (4 * (factorial 3)))
(5 * (4 * (3 * (factorial 2))))
(5 * (4 * (3 * (2 * (factorial 1)))))
(5 * (4 * (3 * (2 * 1))))
(5 * (4 * (3 * 2)))
(5 * (4 * 6))
(5 * 24)
120
this is the first solution that comes to anyone's mind. first; multiply 1 by 2, then multiply the result by 3, until n is reached. more efficient way would be changing the counter and product concurrently, so the process will be;
factorial(5)
(factorial_inner 1 1 5)
(factorial_inner 1 2 5)
(factorial_inner 2 3 5)
(factorial_inner 6 4 5)
(factorial_inner 24 5 5)
(factorial_inner 120 6 5)
120
if we write this as a java code;
int factorial(int n) {
return factorial_inner(1, 1, n);
}
int factorial_inner(int product, int counter, int n) {
if(counter > n) return product;
return factorial_inner(counter*product, counter+1, n);
}
fibonacci numbers
in the post fibonnaci numbers and recursion, i've mentioned about tree recursion. in a simple way, fibonacci numbers can be found using tree recursion.
int fibonacci(int n) {
if(n == 0) return 0;
if(n == 1) return 1;
else return fibonacci(n-1) + fibonacci(n-2);
}
as i've written factorial with an inner recursion, fibonacci numbers can also be written in this way for efficiency.
int fibo(int n) {
return fibo_inner(1, 0, n);
}
int fibo_inner(int a, int b, int n) {
if(n == 0) return b;
return fibo_inner(b+a, a, n-1);
}
exponential
another example would be finding the exponential of a number. let's say we want to compute xn which can be defined as;
xn = x * xn-1
x0 = 1
if we write this definition as a java method;
int exponential(int x, int n) {
if(n == 0) return 1;
return x*exponential(x, n-1);
}
it's very similar to factorial computation. this needs o(n) time, and o(n) space as well. like we did in fibonacci, and factorial we can write this method as follows;
int exponential(int x, int n) {
return exponential_inner(x, n, 1);
}
int exponential_inner(int x, int n, int res) {
if(n == 0) return res;
return exponential_inner(x, n-1, x*res);
}
this version needs o(n) time, and o(1) space, but it can be still improved.in the beginning i said "breaking down the problem into small problems". if we want to find x4, since the algorithm runs in o(n) time, the computation will be;
x * x * x *x;
but it can be computed as follows in two steps;
x2 = x * x;
x4 = x2 * x2
you may wonder "what if n is not even?", then the algorithm can be changed in this way;
xn = (xn/2)2 // if n is even
xn = x * xn-1 // if n is odd
if we write this down as a java method;
int exponential(int x, int n) {
if(n == 0) return 1;
if(isEven(n)) return square(exponential(x, n >> 1));
else return x * (exponential(x, n-1));
}
boolean isEven(int n) {
return (n & 1) == 0;
}
int square(int x) {
return x*x;
}
this algorithm runs logarithmically both in time, and space. the process has o(log n) growth.converting decimal to binary
this problem is way ease. it might be considered as a warm-up problem to recursion.
String dec2bin(StringBuilder s, int n) {
if(n < 1) return s.reverse().toString();
return dec2bin(s.append(n & 1), n >> 1);
}
at first recursion can be found difficult but once you get the idea you'll notice it's ease, and if you're interested in functional programming you'll love it.
some posts you can find information about recursion;