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:

So, to wrap your head around this idea example:

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!

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:

So, to wrap your head around this idea example:

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!