Recursion

Recursion

> LeekScript Tutorial

Prerequisites:

• Obligatory:
• Know how to define a function.
• Recommended:
• Know how to use anonymous functions/closures.
• Useful:
• Have notions of what are abstract data types, in particular the stack. cf: source
• Know what [Memoisization] is(https://leekwars.com/encyclopedia/Optimisation#Pr%C3%A9parer_du_curry)

----

Recursion, broadly speaking, is the ability of an object to refer to itself. In the real world, this is most evident in fractals, as well as when two mirrors are placed face to face. We also find this notion in sentences of the style: "I dream that I dream that I dream." or "I think that I write that I dream that I think that I write...", etc In programming, this mostly manifests with functions that call themselves:

function loop() { loop(); }

The above function is the simplest recursive function there is. When called, it does nothing but call itself. This is the same as using an infinite loop (eg. while(true);). We will use this function as a basic skeleton for all our future recursive functions.

Recursion

Recursion is analogous to deconstruction. It is mainly found in ''Divide and Conquer'' type algorithms. To solve our problem, we start by subdividing it into easier sub-problems to solve, we repeat the process until we find a problem that we know how to solve directly, and from there, we solve the higher problems by combining our previous solutions.

Set Sum from 0 to n

We want to define a function taking an integer n as a parameter and returning the sum of 0 to n (eg. 0 + 1 + ... + n). Taking our basic skeleton, we can start with the following function:

function sumN(n) { sumN(?); return?; }

At the moment we have the following information:

• n is known;
• we can call sumN with a new value;
• we can use the return of the new call;
• sumN must return a number;
• there must be an addition somewhere;
• as for loop, sumN does not stop. We're going to have to figure out how to stop it.

When working recursively, it's always a good idea to start with the stopping condition. In the case of recursion, we want to stop creating subproblems when we've found something we can solve. In this case, the sum of 0 to 0 is something we know how to solve. 0 is therefore our base case, we can directly return the corresponding sum.

function sumN(n) { if (n === 0) { return 0; } else { sumN(?); return?; } }

We now need to figure out how to reach the base case. We could subtract n from itself, but in that case we would not be able to sum the integers between 0 and n, we would only have 0 and n available. We will therefore have to create a sub-problem that can solve a sum with an n closer to our base case.

function sumN(n) { if (n === 0) { return 0; } else { sumN(n - 1); return?; } }

We now only need to do the sum, which was asked of us at the beginning. Here, the sum of 0 to n is also the sum of the sum of 0 to n - 1 and n.

function sumN(n) { if (n === 0) { return 0; } else { return n + sumN(n - 1); } }

With a ternary:

function sumN(n) { return n === 0? 0 : n + sumN(n - 1); }

Feel free to try the code in your Leekwars editor. Perhaps you will discover the main problem with recursion. You can also visualize the execution (in a basic way) on this site.

Corecursion

/!\ Section to redo, what is shown is mostly tail recursion. Unsuitable for multiple branches. /!\ Corecursion is analogous to construction. Unlike in recursion where we seek to reach a base case from our main problem, in corecursion we start directly with our base case, and move towards the solution of the main problem.

Mutual Recursion

We have already covered mutual recursion with mirrors and sentences. In programming, with functions, this translates to two or more functions calling each other. We present below the simplest case of mutual recursion:

function mutualLoop() { mutualHelper(); }

function mut