====== Script recursion ======

===== What is recursion =====

Recursion in programming is a technique used mainly in functional programming languages to break down a problem you have into smaller, identical sub-problems. Recursion simplifies the problem-solving process by allowing the solution to be expressed in terms of a smaller version of the same problem.

The main uses of recursion in programming include:

  * Solving complex problems, because by breaking down a complex problem into smaller, more manageable subproblems, the solution becomes more elegant and easier to understand

  * Divide and conquer algorithms these algorithms follow a recursive structure where the problem is divided into smaller subproblems, solved independently and then combined to obtain the final solution

  * Fractals: Recursion is often employed in generating fractal patterns, where a geometric shape is repeated at different scales within the overall structure, thats because fractals recursively draw one or more transformed copies of the same figure

==== Advantages of recursion ====

  * Simplicity: Recursive solutions can be simpler and easier to understand, especially for certain types of problems

  * Natural for Some Problems: Recursion is a good fit for problems that naturally break down into smaller, similar sub-problems

  * Code Reusability: Recursive functions can be reused in different contexts, and that makes it good as it keeps the code divided in modules

====  Disavangates of recursion ====

  * Stack Overflow: Too much recursion can lead to a "stack overflow"((Imagine you have a tower, this is a stack stacking them up. Each you add a brick (run a function), you add more length. When the stack gets too tall (too many function calls), it falls over – that's a "stack overflow." In programming, it's like the computer is saying, "Whoa, too much! I can't handle all of this.")) ((Wikipedia article [[wp>Stack_overflow| Stack overflow]]))

  * Performance: Recursive solutions may not always be the most efficient, and iterative solutions might be faster.

  * Debugging Challenges: Debugging recursive code can be harder, particularly when dealing with deep levels of recursion.

===== Recursion example =====

  - For the first example, we will do a recursive function that gives us the fibonacchi sequence (( Fibonacci numbers are a sequence of numbers where each number is the sum of the two preceding ones, usually starting with 0 and 1. So, it goes like this: 0, 1, 1, 2, 3, 5, 8, 13, and so on.)) ((Wikipedia article: [[wp>Fibonacci_sequence| Fibonacchi sequence]]))

<code>

function fibRecursion(n)
    if n < 0 then 
        error("Invalid number.")
        return 0
    end
    
    if n <= 1 then
        return n
    else
	return fibRecursion(n-1) + fibRecursion(n-2)
    end
end

</code>

We can see that when the number is less than 0, it will give us an error, when the number is less than 1 and greater than 0 it will return itself, if the number is greater than 1, it will return the sum of (n-1) and (n-2), we can call the function and it will give us the fibonacchi number in the n position

let's add a for loop that prints the numbers from 1 to 12

<code>

function fibRecursion(n)

    if n < 0 then 
        error("Invalid number.")
        return 0
    end
    
    if n <= 1 then
        return n
    else
	return fibRecursion(n-1) + fibRecursion(n-2)
    end
end

for i=1, 12 do
    print("fibonnaci number in the position ".. i.. ": ".. fibRecursion(i))
end

</code>

The fibonacci numbers from 1 to 12 are:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144

when we run the program, we can see that it indeed, gives us those numbers!