Recursion and Stacks

What is Recursion?

Recursion is where a function calls itself.

lets have an example

we are having a box that contains other boxes, and you know there is a key inside one of these boxes. You want to find that key, what would you do?

Here is an approach:

1. Make a pile of boxes to look through.
2. Grab a box, and look through it.
3. If you find a box, add it to the pile to look through later.
4. If you find a key, you are DONE!🎉

This approach uses a while loop, while pile is not empty grab a box, and look through it.

An alternate approach:

1. Look through the box.
2. If you find a box, go to step 1.
3. If you find a key, you are DONE!🎉

This second approach uses recursion.

be careful using recursion as it may end up with infinite loop. 
That's why recursive functions has two parts
1. The base case -> function doesn't call itself again.
2. The recursive case -> function calls itself.  

Stacks

Stack is an important concept in general programming, and also important to understand when using recursion.
let's have an example
we are having a stack of sticky notes. when we insert an item we add it to the top of the stack. when we read an item we only read the topmost item, and it is taken of the stack.
so our todo has two actions push(insert) and pop(remove)
stack is last in first out data structures

The Call Stack

The computer uses a stack internally called the call stack let's see how it works:
example

This greet() function calls two functions greet2() and bye().

1. suppose you call greet('maggie') your computer allocates a box in memory for that function call.
2. variable name is set to maggie inside that memory box.

every time you make a function call, your computer saves variables for that call in memory like the previous steps. Computer uses a stack of these boxes on top of each other every time you call a new function it is added to the top until it is finished then removed, that means the first function called the last to be finished.

Comments

[YiSaleh]

To the point 👏