PDA

View Full Version : A Guide to Recursion

Kevin
03-08-2013, 01:49 AM
Recursion Simplified

Definition:
Recursion is an amazing technique in any programmer's arsenal. As defined by wikipedia (for what that's worth): "Recursion is the process of repeating items in a self-similar way." In programming, recursion is the act of a method calling itself in order to complete its calculations. Most often, this is a method of asking for simpler and simpler questions until it has an answer each successive, more complicated portion has a simpler answer. So, in essence, it's calculating its own answer from its own answer.

However, recursion has its own disadvantages. For example, every recursive call increases the size of the stack and spends slightly more time per iteration moving around in code as opposed to a directly iterative solution (To read more about the the stack and background memory/computation efficiencies, read another one of my tutorials here (http://villavu.com/forum/showthread.php?t=95007). However, in certain circumstances, problems can only be solved recursively (or at least the efficiency of recursion is far greater than that of iteratively), such as seen in the MergeSort (http://en.wikipedia.org/wiki/Merge_sort) algorithm.

Fibonacci:
In math, there's a pattern of numbers known as the Fibonacci sequence. The Fibonacci sequence is a pattern where any given number in the sequence is equivalent to the summation of the 2 previous numbers in the sequence. Also, position 0 of Fibonacci has the value of 0 and 1st Fibonacci has the value of 1.

Example:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34

0+1=1, 1+1=2, 1+2=3, 2+3=5, 3+5=8, etc...

So, Fib(5)=Fib(4)+Fib(3), and each of those answers is equivalent to the comparison prior. This could be hard coded entirely, but that's not very efficient, so we have recursion to help us out.

In Code:
function Fib(num: integer): integer;
begin
if(num=0)then
begin
Result:= 0;
end else if(num=1)then begin
Result:= 1;
end else
Result:= Fib(num-1) + Fib(num-2);
end;

See, that wasn't so terrible, now what it? Although, I will admit now that this is NOT the most efficient solution to the Fibonacci sequence, however it is the simplest. If desired, I can go into more detail on more complex and faster solutions.

Extended Euclidean Algorithm:
You can read about EEA here (http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm). I'm sorry if you don't understand the process, but if you ask me more specialized questions I can try and answer those to the best of my ability.

Simplified greatly, it's used to find the inverse modularity of two numbers, or in advanced computer encryption/decryption algorithms. The most common example I am familiar with is in RSA encryption (http://en.wikipedia.org/wiki/RSA_%28algorithm%29#Key_generation), which happens to be one of the most commonly used encryption algorithms in all internet based network activity. However, this is partially here for NKN to get a better idea of how this works and how recursion can help.

Example:
120x + 23y = 1
X=-9 Y=47

In Code:
function EEA(a,b: integer): TPoint; //Tpoint storage for 2 return integers
var
q,r,s,t: integer;
pt: Tpoint;
begin
if(b=0) then
begin
Result:= Point(1, 0);
end else begin
q:= a/b;
r:=a mod b;
pt:= EEA(b, r);
s:= pt.x;
t:= pt.y;
Result.x:= t;
Result.y:= (s - (q * t));
end;
end;

I hope this helps, and if it doesn't ask away and I will do my best to answer!

Le Jingle
03-08-2013, 02:34 AM
What about the time/space trade off under BigO (memory, stack, speed, etc.), its relationship to loops in general, and modern uses in today's job industry (ex. ray tracing)?

I'm sure there's plenty more to elaborate on too, found the examples insufficient to my [learning] appetite (more so personal observation, than criticism; I still have value of reading this as I'm sure it helps others learn via example).

Kevin
03-08-2013, 03:18 AM
What about the time/space trade off under BigO (memory, stack, speed, etc.), its relationship to loops in general, and modern uses in today's job industry (ex. ray tracing)?

I'm sure there's plenty more to elaborate on too, found the examples insufficient to my [learning] appetite (more so personal observation, than criticism; I still have value of reading this as I'm sure it helps others learn via example).

I'll include mention of the algorithmic performances versus an iterative version of this code and I'm trying to limit myself to simple examples, but perhaps I'll include mention of RSA encryption as I think that's a simple use of EEA.

If you have specific example, I can add it. I might work on a picture to help explain how recursion.