Results 1 to 3 of 3

Thread: A Guide to Recursion

  1. #1
    Join Date
    Sep 2012
    Location
    Here.
    Posts
    2,007
    Mentioned
    88 Post(s)
    Quoted
    1014 Post(s)

    Default A Guide to Recursion

    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. 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 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:
    Simba 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. 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, 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:
    Simba 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!

  2. #2
    Join Date
    Feb 2012
    Location
    Wonderland
    Posts
    1,988
    Mentioned
    41 Post(s)
    Quoted
    272 Post(s)

    Default

    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).

  3. #3
    Join Date
    Sep 2012
    Location
    Here.
    Posts
    2,007
    Mentioned
    88 Post(s)
    Quoted
    1014 Post(s)

    Default

    Quote Originally Posted by Le Jingle View Post
    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.

Thread Information

Users Browsing this Thread

There are currently 1 users browsing this thread. (0 members and 1 guests)

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •