How does recursion really works in computer science?

22 views

How does recursion really works in computer science?

In: 0

Most implementations of recursion use an actual subroutine jump to save current state, invoke the function, and continue after it returns. There are optimizations that some compilers can make to exploit that the function is calling itself, but not all compilers do that.

Imagine you have a man that is neither smart nor dumb, he will simply follow instructions to the letter, this is a computer.

You hand him a stick and tell him: “Break this stick in half, now give me the sticks” he takes the stick, breaks it in half, and gives it back to you. This is an example of a non-recursive function since you give him precise instructions on what to do and a end result.

You hand him a stick and tell him: “Whenever you have a stick, break it in half” he takes the stick, breaks it in half, looks down and sees he now has 2 sticks, which he each breaks in half, then he looks down and sees he now has 4 sticks… This will go on forever until he has a stick so small he can no longer break it in half. Then he comes to you to tell you he couldn’t do his job. This is an example of a recursive function.

Recursion can be an amazing tool to use but is impossible to fully predict in more complex instructions, it is any instruction that will repeat itself until certain conditions are met (or not) you can use it to calculate absurdly large numbers (A good example is Pi) but there is never really a guarantee that it will finish what it was told to do without causing problems (errors)

Recursion just means something that calls itself.

Here’s an example: List all the files in all subfolders of a directory.

Your code outline might look something like this:

Function: parseFolder

Logic: List all files in the folder. Then, for each subfolder of this folder, call parseFolder.

Practically, what this is going to do is list all the files in each folder, go into the subfolders of that folder and list those files, go into the subfolders of *that* folder and list all the folders, etc, until there are no more subfolders to explore.

Depends on the language you are using but most operate the same way.

Functions take up space in the ram to operate so each function has it’s own dedicated space. When you call a function it creates that space for the function to inhabit. When a function calls itself, it creates another space in the ram for the this function to inhabit. This continues until (hopefully) a base case returns (where the space is unreserved and can be used for more stuff). Otherwise it’ll keep on creating new space on the ram for functions until you quite literally run out, although modern cpus will just kill the program before that happens.

This explanation is of course wildly oversimplified but the concept is like that.

Recursion works for computer science classes, as a way of misleading dev students about what actually goes on in software development.

In industry I’m not sure if I’ve ever seen a recursive function written by anyone other than a total beginner.

Recursion makes debugging extremely difficult and problems which are suitable for recursion can often be solved by having two functions and a couple of variables about state. One function manages the state variable and the other function actually does processing and the managing function has a loop that updates the state variables and keeps calling the processing function until the state variables represent a success state.

There is another use for recursion in industry which is when a tech company wants to know how good you are at writing unreadable, untestable, confusing “genius code”, they’ll give you some recursion problem to try it with.