- A function is said to be recursive if it calls itself (self-referential). e.g. factorial function f(x) = (x<=1?1:x*f(x-1))
- Programming is simply a rewriting of the definition using the language
- Correctness of program can be proved mathematically
- Use of stack to keep the successive generations of local variables and parameters requires more memory space and slower when executed
public class TestFactorial {
private static void main(String[] args) {
int x = Integer.parseInt(args[0]);
try {
System.out.println("Factorial of " + x +" is " + factorial(x));
} catch (StackOverflowError soe) {
System.out.println(soe.toString() + " when x is " + x);
}
}
private static int factorial(int x) {
if (x <= 1)
return 1;
else return x * factorial(x-1);
}
}
- Fibonacci numbers e.g. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34
f(n) = n if n == 0 or n == 1
f(n) = f(n-2) + f(n-1) if n > 1
public static int Fib(int n) {
if (n <= 0)
return 0;
else if (n == 1)
return 1;
else return Fib(n-1) + Fib(n-2);
}
- Iterative version
public static int Fib(int n) {
int i;
int twoback; // second previous number, F_{i-2}
int oneback; // previous number, F_{i-1}
int current; // current number, F_{i}
if (n <= 0)
return 0;
else if (n == 1)
return 1;
else {
twoback = 0;
oneback = 1;
for (i = 2; i <= n; i++) {
current = twoback + oneback;
twoback = oneback;
oneback = current;
}
return current;
}
}
- Tower of Hanoi
private static void move(int n, int from, int to, int temp) {
if (n == 1)
System.out.println("Move top disk from peg " + from + " to peg " + to);
else {
move(n - 1, from, temp, to);
move(1, from, to, temp);
move(n - 1, temp, to, from);
}
}
- Self-referential structures (Node of a Linked List)
class Node {
int data;
Node next;
}