Logic & Computation Recursion Lecture 1
public class recursion {
public static void main(String[] args)
{
// int st = 100;
// recurse(st);
int term = 6;
System.out.println(Fib(term));
System.out.println(recurseFib(term));
}
/*
* Recursion is the epitome of Computer Science, and the cultivation of Formal Logic.
* The process in which a method calls itself directly or indirectly is called recursion.
* Through recursion, certain problems that were impossible to do via for loops,
* are solved relatively easily. What makes recursion so powerful is its ability to
* copy itself and solving smaller subproblems through near infinite copies.
* Each copy tackles a small iteration, and returns to its sender the necessary data
* for it to solve its own problem.
*
* Visualizing recursion can be pretty difficult. Simple recursive methods work
* through step by step in chronological order, but practical recursive methods
* usually work in a 'reverse call' order, where the methods first create
* copies, and then wait for the created copies to finish their work. Usually these
* copies will make their own copies, which make more copies, and so on so forth
* until the method finally reaches an exit condition, to which it gathers its data,
* and returns a value to its sender, which then goes back in reverse order until
* the data eventually reaches the original sender.
*
* Goes something like this
*
* Original sender (root) --> copy --> copy --> etc. --> end case
* Original sender <-- copy <-- copy <-- etc. <-- data.
*
* But with many more copies, in multiple separate paths.
*
* To create a recursive method, a few things must occur for the method to work.
*
* 1. You MUST call the method somewhere inside of it. By calling the method inside
* of itself, you allow the method to create copies whenever conditions are met. Usually,
* you regurgitate its given variables, and increment them by the appropriate amount
* before passing them onwards to the recursed method called.
*
* 2. You MUST place your exit conditions in your method. Your exit conditions
* are what inform your recursive method when to stop, and it is what allows
* the copies to send back data to execute their code. Without proper exit conditions
* your method will go on forever, and you will be forever haunted by the dry and non-witty
* humor of programmers and their relentless recursive """jokes""".
*
* 3. For the love of everything that is holy and pure, PLEASE MAKE SURE YOUR
* RECURSION METHOD TERMINATES. Use if/else statements to force your recursive method
* to check for its exit conditions, which are what stop the iterative process.
*
* 4. Combine the solutions of the 'copies' so that they actually work together
* and return the solution to your problem.
*
* You will see these steps in the recursive method below, which is the
* Fibonnaci Sequence in recursive form.
*/
//recursive methods work the same way as normal methods with their parameters.
public static int recurseFib(int term)
{
//This is the exit condition. If the value of 'term' is ever less than or equal
//to 1, return it. When this activates, the recursive call at the bottom doesn't occur.
if(term <= 1)
{
return term;
}
/*
* This is the recursive case which allows the method to create copies.
* If the if statement above never procs, this bottom line of code runs
* and creates two copies of the original method. Notice how we are decrementing
* the value of 'term' with different values for each recursive call, and how
* we are returing the sum of the result of each case.
* Each copy will run and do their own thing, and when they eventually end up with a value
* it will return said value, and add it with the other copy's value, via that
* reverse call order.
*/
return recurseFib(term-1) + recurseFib(term-2);
}
public static int Fib(int term)
{
int fib1 = 1;
int fib2 = 0;
for(int i = 1; i < term; i++)
{
int placeholder = fib1;
fib1 = fib1 + fib2;
fib2 = placeholder;
}
return fib1;
}
public static int recurse(int x)
{
if(x > -1)
{
System.out.println(x);
x--;
recurse(x);
}
return x;
}
}