While recursive functions are convenient, they also have drawbacks. As a result, recursive functions have long been converted to non-recursive functions. The conversion itself was done, but it was random and I didn't think theoretically why it could be converted. I wanted to think about the conversion process theoretically, but I couldn't take the opportunity. Meanwhile, the article on recursive functions was on the trend, so I started writing articles. (It's been a long time since I left it alone) Another factor is that I was writing another program and realized the importance of the stack.

However, it does not deny the usefulness of recursive functions. I love recursive functions.

The programming language can be anything, so I'll use Python. I will not explain the algorithm itself used to create the recursive program. Therefore, we are targeting those who understand Python and understand (examine) algorithms.

The stack that controls the execution of the program is called the call stack (Call Statck). It is also called an execution stack, a control stack, a function stack, and so on. In this article, we will use the call stack. Also, the stack as a data structure is simply called the stack.

Recursive functions use the call stack by calling the function. There is an upper limit to the capacity that can be stored in the call stack. The capacity can be changed by changing the settings of the compiler, etc., but it is still finite. (I've been touching it lately, so I don't know how flexible it is.) If the call stack capacity is exceeded, a stack overflow will occur and program execution will stop. Recursive functions, in principle, tend to consume large amounts of call stacks and cause stack overflows. It depends on the settings, but in my experience, which is not so many, it is easy to use up the call stack and cause a stack overflow. (Maybe it's because of your dung program) Therefore, it tends to be avoided.

On the other hand, the heap space used by the stack is relatively more flexible than the call stack. (I think this also depends on the settings and the program to be created) Therefore, we will switch to using the stack.

Recently, there are compilers that have a function called tail recursion optimization that converts tail recursion into a loop structure. It's getting better without having to worry too much. It's becoming more convenient.

In this article, I think it's a typical conversion method, but I'd like to consider making a recursive function a non-recursive function using the stack. This is an image of switching the use of the call stack to the use of the stack.

First, consider a simple factorial as an example.

Implementing factorial using recursion gives:

```
def factorialR(n) :
if n == 0 :
return 1
return n * factorialR(n-1)
```

Let's illustrate what the call stack looks like when this function is executed with n = 5.
It is not a strict operation but an image movement.
When the function is executed, it first pushes the call itself `factorialR (5)`

to the call stack.
`factorialR (5)`

is converted to`5 * factorialR (4)`

when executed.

Bottom Top | |
---|---|

f(5) |

Bottom Top | |
---|---|

5 * f(4) |

It then calls `factorialR (4)`

and pushes it onto the call stack.
`factorialR (4)`

is converted to`4 * factorialR (3)`

when executed.

Bottom | Top |
---|---|

5 * f(4) | f(4) |

Bottom | Top |
---|---|

5 * f(4) | 4 * f(3) |

Hereafter, it works in the same way.

Bottom | Top | |
---|---|---|

5 * f(4) | 4 * f(3) | f(3) |

Bottom | Top | |
---|---|---|

5 * f(4) | 4 * f(3) | 3 * f(2) |

Bottom | Top | ||
---|---|---|---|

5 * f(4) | 4 * f(3) | 3 * f(2) | f(2) |

Bottom | Top | ||
---|---|---|---|

5 * f(4) | 4 * f(3) | 3 * f(2) | 2 * f(1) |

Bottom | Top | |||
---|---|---|---|---|

5 * f(4) | 4 * f(3) | 3 * f(2) | 2 * f(1) | f(1) |

Bottom | Top | |||
---|---|---|---|---|

5 * f(4) | 4 * f(3) | 3 * f(2) | 2 * f(1) | 1 * f(0) |

The recursive call continued until n = 0.

Bottom | Top | ||||
---|---|---|---|---|---|

5 * f(4) | 4 * f(3) | 3 * f(2) | 2 * f(1) | 1 * f(0) | f(0) |

If n = 0, 1 is returned.

Bottom | Top | ||||
---|---|---|---|---|---|

5 * f(4) | 4 * f(3) | 3 * f(2) | 2 * f(1) | 1 * f(0) | 1 |

When `factorialR (0)`

is executed and 1 is returned, the call stack is lowered by one.
Then, it returns to the time of calling n = 1, `1 * factorialR (0)`

is resolved, and `1 * 1 = 1`

is returned.

Bottom | Top | |||
---|---|---|---|---|

5 * f(4) | 4 * f(3) | 3 * f(2) | 2 * f(1) | 1 |

Similarly, the return of the previous execution result lowers the call stack by one.
It returns to the point where n = 2 is called and `2 * factorialR (1)`

is resolved and `2 * 1 = 2`

is returned.
Hereafter, it works in the same way.

Bottom | Top | ||
---|---|---|---|

5 * f(4) | 4 * f(3) | 3 * f(2) | 2 |

Bottom | Top | |
---|---|---|

5 * f(4) | 4 * f(3) | 6 |

Bottom | Top |
---|---|

5 * f(4) | 24 |

Bottom Top | |
---|---|

120 |

Finally, `5 * factorialR (4) = 5 * 24 = 120`

and 120 is returned.

The recursive version of factorial makes function calls recursively, so the calls are pushed onto the call stack.
I want to keep the structure of the function as it is and not use the call stack.
The above function required the calculation result in the middle and the argument used for the next function call to calculate the factorial.
Therefore, try stacking the calculation result in the middle into one variable and the value used for the next function call on the stack.
In the case of `5 * f (4)`

, 5 is put on the variable and 4 is put on the stack.
Based on this idea, I would like to make a non-recursive version.

Again, let's illustrate the movement of the stack when n = 5. When the function starts, it first pushes 5 onto the stack. Also, set the variable Result that saves the calculation result in the middle to 1.

Bottom Top | Result |
---|---|

5 | 1 |

The next step is to pop the stack and retrieve the value 5.
Then multiply Result by the retrieved value.
Finally, push the value 4 of `5-1 = 4`

onto the stack.

Bottom Top | Result |
---|---|

4 | 5 |

The next step is to pop the stack and retrieve the value 4.
Then multiply Result by the retrieved value.
Finally, push the value 3 of `5-1 = 3`

onto the stack.

Bottom Top | Result |
---|---|

3 | 20 |

Hereafter, it works in the same way.

Bottom Top | Result |
---|---|

2 | 60 |

Bottom Top | Result |
---|---|

1 | 120 |

Bottom Top | Result |
---|---|

0 | 120 |

Pop the value 0 and then multiply Result by 1. If 0, there is no next value to push onto the stack.

Bottom Top | Result |
---|---|

120 |

Since the stack is gone, the Result value of 120 is sought as the factorial answer for n = 5. I think you can find the meaning of using the stack because the factorial is simple. However, I do this for the generalization of the conversion. Let's make a function based on this. To be honest, would it be as follows?

```
def factorialL(n):
stack = [n]
result = 1
current = 0
while len(stack) > 0:
current = stack.pop()
if current <= 0:
current = 1
else :
stack.append(current - 1)
result *= current
return result
```

Consider an implementation that reproduces the behavior of the recursive version of the call stack on the stack. Let's move the stack as follows.

Bottom | Top |
---|---|

5 | 4 |

Bottom | Top | |
---|---|---|

5 | 4 | 3 |

Bottom | Top | ||
---|---|---|---|

5 | 4 | 3 | 2 |

Bottom | Top | |||
---|---|---|---|---|

5 | 4 | 3 | 2 | 1 |

When n = 0, it is `0! = 1`

, so 1 is fixed.

Bottom | Top | ||||
---|---|---|---|---|---|

5 | 4 | 3 | 2 | 1 | 1 |

Then pop the confirmed 1 and break one stack. Save this popped 1 as a Result.

Bottom | Top | Result | |||
---|---|---|---|---|---|

5 | 4 | 3 | 2 | 1 | 1 |

It then pops the Top value of 1 and breaks one stack.
Calculate `1 * 1`

using the 1 you saved earlier and the 1 you just popped, and save` 1`

as the Result.
This confirms the value of n = 1.
Hereafter, it will be executed in the same way.

Bottom | Top | Result | ||
---|---|---|---|---|

5 | 4 | 3 | 2 | 1 |

Pop the Top value 2 and multiply it by the Result value 1 to get the result 2 in the Result.

Bottom | Top | Result | |
---|---|---|---|

5 | 4 | 3 | 2 |

Pop the Top value 3 and multiply it by the Result value 2 to get the result 6 in the Result.

Bottom | Top | Result |
---|---|---|

5 | 4 | 6 |

Pop the Top value 4 and multiply it by the Result value 6 to get the result 24 in the Result.

Bottom | Result |
---|---|

5 | 24 |

Pop the Top value 5 and multiply it by the Result value 24 to get the result 120 in the Result.

Result | |
---|---|

120 |

Since the stack is gone, the Result value of 120 is sought as the factorial answer for n = 5.

In this case, would it be as follows?

```
def factorialL(n):
stack = []
for i in range(n, 0, -1) :
stack.append(i)
result = 1
for i in range(len(stack)) :
top = stack.pop()
result *= top
return result
```

A slightly cleaner implementation looks like this:

```
def factorial1(n):
result = 1
for i in range(1, n + 1) :
result *= i
return result
```

```
from functools import reduce
def factorial2(n):
return reduce(lambda a, b: a * b, range(1, n + 1), 1)
```

Next, I would like to take the Fibonacci sequence as an example.

A typical implementation using Fibonacci sequence recursion would look like this: The big difference from factorial is that you call yourself twice in one run.

```
def fibonacciR(n) :
if n == 0 or n == 1 :
return n
return fibonacciR(n - 2) + fibonacciR(n - 1)
```

Let's illustrate the state of the call stack when n = 5, as in factorial.
When the function is executed, `fibonacciR (5)`

is first pushed onto the call stack.
Then it is converted to `fibonacciR (3) + fibonacciR (4)`

.

Bottom Top | |
---|---|

f(5) |

Bottom Top | |
---|---|

f(3) + f(4) |

Then `fibonacciR (3)`

is called and pushed onto the call stack.
When executed, it will be converted to `fibonacciR (1) + fibonacciR (2)`

.

Bottom | Top |
---|---|

f(3) + f(4) | f(3) |

Bottom | Top |
---|---|

f(3) + f(4) | f(1) + f(2) |

Then `fibonacciR (1)`

is called and pushed onto the call stack.
`fibonacciR (1)`

returns 1 when executed.
This partially resolves `fibonacciR (1) + fibonacciR (2)`

when calling `fibonacciR (3)`

to become `1 + fibonacciR (2)`

.

Bottom | Top | |
---|---|---|

f(3) + f(4) | f(1) + f(2) | f(1) |

Bottom | Top | |
---|---|---|

f(3) + f(4) | f(1) + f(2) | 1 |

Bottom | Top |
---|---|

f(3) + f(4) | 1 + f(2) |

To resolve `fibonacciR (2)`

, it is called and pushed onto the call stack.
When executed, it will be converted to `fibonacciR (0) + fibonacciR (1)`

.

Bottom | Top | |
---|---|---|

f(3) + f(4) | 1 + f(2) | f(2) |

Bottom | Top | |
---|---|---|

f(3) + f(4) | 1 + f(2) | f(0) + f(1) |

`fibonacciR (0)`

is called and pushed onto the call stack.
`fibonacciR (0)`

returns 0 when executed.
This partially resolves `fibonacciR (0) + fibonacciR (1)`

when calling `fibonacciR (2)`

to become `0 + fibonacciR (1)`

.

Bottom | Top | ||
---|---|---|---|

f(3) + f(4) | 1 + f(2) | f(0) + f(1) | f(0) |

Bottom | Top | ||
---|---|---|---|

f(3) + f(4) | 1 + f(2) | f(0) + f(1) | 0 |

Bottom | Top | |
---|---|---|

f(3) + f(4) | 1 + f(2) | 0 + f(1) |

Similarly, `fibonacciR (1)`

is called and pushed onto the call stack.
`fibonacciR (1)`

returns 1 when executed.
This resolves `0 + fibonacciR (1)`

when calling `fibonacciR (2)`

to `0 + 1 = 1`

.

Bottom | Top | ||
---|---|---|---|

f(3) + f(4) | 1 + f(2) | 0 + f(1) | f(1) |

Bottom | Top | ||
---|---|---|---|

f(3) + f(4) | 1 + f(2) | 0 + f(1) | 1 |

Bottom | Top | |
---|---|---|

f(3) + f(4) | 1 + f(2) | 0 + 1 |

`1 + fibonacciR (1)`

when calling `fibonacciR (3)`

is resolved to `1 + 1 = 2`

.

Bottom | Top |
---|---|

f(3) + f(4) | 1 + 1 |

Part of `fibonacciR (3) + fibonacciR (4)`

when calling `fibonacciR (5)`

is resolved to become `2 + fibonacciR (4)`

.

Bottom Top | |
---|---|

2 + f(4) |

It works in the same way below.

Bottom | Top |
---|---|

2 + f(4) | f(4) |

Bottom | Top |
---|---|

2 + f(4) | f(2) + f(3) |

Bottom | Top | |
---|---|---|

2 + f(4) | f(2) + f(3) | f(2) |

Bottom | Top | |
---|---|---|

2 + f(4) | f(2) + f(3) | f(1) + f(0) |

Bottom | Top | ||
---|---|---|---|

2 + f(4) | f(2) + f(3) | f(1) + f(0) | f(1) |

Bottom | Top | ||
---|---|---|---|

2 + f(4) | f(2) + f(3) | f(1) + f(0) | 1 |

Bottom | Top | ||
---|---|---|---|

2 + f(4) | f(2) + f(3) | 1 + f(0) | f(0) |

Bottom | Top | ||
---|---|---|---|

2 + f(4) | f(2) + f(3) | 1 + f(0) | 0 |

Bottom | Top | |
---|---|---|

2 + f(4) | f(2) + f(3) | 1 |

Bottom | Top |
---|---|

2 + f(4) | 1 + f(3) |

Bottom | Top | |
---|---|---|

2 + f(4) | 1 + f(3) | f(3) |

Bottom | Top | |
---|---|---|

2 + f(4) | 1 + f(3) | f(1) + f(2) |

Bottom | Top | ||
---|---|---|---|

2 + f(4) | 1 + f(3) | f(1) + f(2) | f(1) |

Bottom | Top | ||
---|---|---|---|

2 + f(4) | 1 + f(3) | f(1) + f(2) | 1 |

Bottom | Top | |
---|---|---|

2 + f(4) | 1 + f(3) | 1 + f(2) |

Bottom | Top | ||
---|---|---|---|

2 + f(4) | 1 + f(3) | 1 + f(2) | f(2) |

Bottom | Top | ||
---|---|---|---|

2 + f(4) | 1 + f(3) | 1 + f(2) | f(0) + f(1) |

Bottom | Top | |||
---|---|---|---|---|

2 + f(4) | 1 + f(3) | 1 + f(2) | f(0) + f(1) | f(0) |

Bottom | Top | |||
---|---|---|---|---|

2 + f(4) | 1 + f(3) | 1 + f(2) | f(0) + f(1) | 0 |

Bottom | Top | ||
---|---|---|---|

2 + f(4) | 1 + f(3) | 1 + f(2) | 0 + f(1) |

Bottom | Top | |||
---|---|---|---|---|

2 + f(4) | 1 + f(3) | 1 + f(2) | 0 + f(1) | f(1) |

Bottom | Top | |||
---|---|---|---|---|

2 + f(4) | 1 + f(3) | 1 + f(2) | 0 + f(1) | 1 |

Bottom | Top | ||
---|---|---|---|

2 + f(4) | 1 + f(3) | 1 + f(2) | 0 + 1 |

Bottom | Top | |
---|---|---|

2 + f(4) | 1 + f(3) | 1 + 1 |

Bottom | Top |
---|---|

2 + f(4) | 1 + 2 |

Bottom Top | |
---|---|

2 + 3 |

Bottom Top | |
---|---|

5 |

It works as above and returns the value 5 when n = 5. I've described it for a long time, but this is how the call stack works. This alone is difficult to understand, so I would like to use a binary tree to represent the movement of this call stack.

Expressed as a binary tree, it is as follows.

```
graph TB;
0[5]---1[3]
0---2[4]
1---3[1]
1---4[2]
4---5[0]
4---6[1]
2---7[2]
2---8[3]
7---9[0]
7---10[1]
8---11[1]
8---12[2]
12---13[0]
12---14[1]
```

You can see that the depth of the call stack corresponds to the depth of the binary tree. You can also see that the order in which the values resolve corresponds to the search order of the binary tree depth-first search. Binary depth-first search is often described as being implemented using a stack. Here, it is implemented using the call stack.

Now I would like to make a non-recursive version.

The recursive version of the Fibonacci sequence is also a simple function, and there is no calculation result in the middle. So what to put on the stack is to put the arguments passed to the function on the stack.

Let's illustrate the stacking situation when n = 5 as before. When it starts running, it pushes the first given argument 5 onto the stack.

Bottom Top | |
---|---|

5 |

The next step is to pop the stack and pop out 5.
5 cannot determine the value from the Fibonacci sequence recurrence formula.
Instead, we'll ask for `n-2`

and` n-1`

.
In other words, push `5-2 = 3`

and` 5-1 = 4`

to the stack respectively.
I will push from the largest number first.

Bottom | Top |
---|---|

4 | 3 |

The next step is to pop the stack and pop out 3. 3 cannot determine the value, so push 1 and 2 respectively instead.

Bottom | Top | |
---|---|---|

4 | 2 | 1 |

The next step is to pop the stack and pull the 1. 1 can be determined as a value, so save it as a Result.

Bottom | Top | Result |
---|---|---|

4 | 2 | 1 |

The next step is to pop the stack and pop out 2. 2 cannot determine the value, so instead push 0, 1 respectively.

Bottom | Top | Result | |
---|---|---|---|

4 | 1 | 0 | 1 |

The next step is to pop the stack and pull 0. Since 0 can be confirmed as a value, add it to Result and save it.

Bottom | Top | Result |
---|---|---|

4 | 1 | 1 |

The next step is to pop the stack and pull the 1. Since 1 can be determined as a value, add it to Result and save it.

Bottom Top | Result |
---|---|

4 | 2 |

Hereafter, it works in the same way.

Bottom | Top | Result |
---|---|---|

3 | 2 | 2 |

Bottom | Top | Result | |
---|---|---|---|

3 | 1 | 0 | 2 |

Bottom | Top | Result |
---|---|---|

3 | 1 | 2 |

Bottom Top | Result |
---|---|

3 | 3 |

Bottom | Top | Result |
---|---|---|

2 | 1 | 3 |

Bottom Top | Result |
---|---|

2 | 4 |

Bottom | Top | Result |
---|---|---|

1 | 0 | 4 |

Bottom Top | Result |
---|---|

1 | 4 |

Result | |
---|---|

5 |

It works as above, and it also returns the value 5 when n = 5. I would like to implement this honestly again.

```
def fibonacciL(n) :
result = 0
current = 0
stack = [n]
while len(stack) > 0 :
current = stack.pop()
if current == 1 or current == 0 :
result += current
else :
stack.append(current-1)
stack.append(current-2)
return result
```

I settled on an implementation similar to factorial. (Although I'm trying to have a similar implementation)

If you want only the answer without being aware of the stack, you can also do the following.
In the case of the stack, it was calculated from the one with the larger coefficient of the recurrence formula, such as `n-> n-1-> n-2-> ...-> 0`

.
This is calculated from the one with the smaller coefficient, such as `0-> 1-> ...-> n`

.

```
def fibonacciL2(n):
if n == 0:
return 0
x, y = 0, 1
for _ in range(n - 1):
x, y = y, x + y
return y
```

Next, consider quicksort.

I tried to implement quicksort recursively as follows.
I am trying to get duplicate values.
I think there are some differences from the typical implementation, but I think it is a quicksort.
I've included `print ()`

to show the sorting process.
We also define and use auxiliary functions for that purpose.
ʻIsSorted ()` determines if it is sorted.

```
def isSorted(lt):
b = lt[0]
for x in lt:
if b > x:
return False
b = x
return True
def getListIndeces(lt, s=0):
if len(lt) == 0:
return "><"
maxLen = len(str(max(lt)))
text = reduce(lambda x, y: x + y, [f"{i+s:{maxLen}}, " for i, x in enumerate(lt)], ">")
return f"{text[:-2]}<"
def listToFormatedString(lt):
if len(lt) == 0:
return "[]"
maxLen = len(str(max(lt)))
text = reduce(lambda x, y: x + y, [f"{x:{maxLen}}, " for x in lt], "[")
return f"{text[:-2]}]"
def getPivot(lt, l, r):
return lt[l + int((r - l) / 2)]
def quickSort(lt):
_quickSort(lt, 0, len(lt) - 1)
def _quickSort(lt, l, r):
if l >= r:
print(f" {getListIndeces(lt[l:r+1], s=l)}, l: {l}, r: {r}\nr: {listToFormatedString(lt[l:r+1])}")
return
i = l
j = r
p = getPivot(lt, l, r)
print(f" {getListIndeces(lt[l:r+1], s=l)}, l: {l}, r: {r}, p: {p}\ns: {listToFormatedString(lt[l:r+1])}")
while i < j:
while lt[i] < p:
i += 1
while lt[j] > p:
j -= 1
if i < j:
if lt[i] == lt[j]:
j -= 1
else:
lt[i], lt[j] = lt[j], lt[i]
print(f"p: {listToFormatedString(lt[l:r+1])}, {i}: {lt[j]}, {j}: {lt[i]}")
_quickSort(lt, l, i - 1)
_quickSort(lt, j + 1, r)
```

Give `[7, 2, 1, 4, 6, 0, 8, 5, 9, 3]`

as an argument and execute it.

```
lt = [7, 2, 1, 4, 6, 0, 8, 5, 9, 3]
quickSort(lt)
print(lt, isSorted(lt))
```

Then, the following execution result will be displayed.

```
>0, 1, 2, 3, 4, 5, 6, 7, 8, 9<, l: 0, r: 9, p: 6
s: [7, 2, 1, 4, 6, 0, 8, 5, 9, 3]
p: [3, 2, 1, 4, 6, 0, 8, 5, 9, 7], 0: 7, 9: 3
p: [3, 2, 1, 4, 5, 0, 8, 6, 9, 7], 4: 6, 7: 5
p: [3, 2, 1, 4, 5, 0, 6, 8, 9, 7], 6: 8, 7: 6
p: [3, 2, 1, 4, 5, 0, 6, 8, 9, 7], 6: 6, 6: 6
>0, 1, 2, 3, 4, 5<, l: 0, r: 5, p: 1
s: [3, 2, 1, 4, 5, 0]
p: [0, 2, 1, 4, 5, 3], 0: 3, 5: 0
p: [0, 1, 2, 4, 5, 3], 1: 2, 2: 1
p: [0, 1, 2, 4, 5, 3], 1: 1, 1: 1
r: >0<, l: 0, r: 0
r: [0]
>2, 3, 4, 5<, l: 2, r: 5, p: 4
s: [2, 4, 5, 3]
p: [2, 3, 5, 4], 3: 4, 5: 3
p: [2, 3, 4, 5], 4: 5, 5: 4
p: [2, 3, 4, 5], 4: 4, 4: 4
>2, 3<, l: 2, r: 3, p: 2
s: [2, 3]
p: [2, 3], 2: 2, 2: 2
r: ><, l: 2, r: 1
r: []
r: >3<, l: 3, r: 3
r: [3]
r: >5<, l: 5, r: 5
r: [5]
>7, 8, 9<, l: 7, r: 9, p: 9
s: [8, 9, 7]
p: [8, 7, 9], 8: 9, 9: 7
p: [8, 7, 9], 9: 9, 9: 9
>7, 8<, l: 7, r: 8, p: 8
s: [8, 7]
p: [7, 8], 7: 8, 8: 7
p: [7, 8], 8: 8, 8: 8
r: >7<, l: 7, r: 7
r: [7]
r: ><, l: 9, r: 8
r: []
r: ><, l: 10, r: 9
r: []
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] True
```

Quicksort also illustrates the movement of the call stack.
First, it is pushed to the call stack as `f (lt)`

.

Bottom Top | |
---|---|

`f(lt)` |

6 is initially selected as the pivot, values less than 6 are moved to the front of the list, and values greater than 6 are moved to the back of the list.
As a result of sorting, since the boundary index is 6, `quickSort ()`

is executed at `lt [0: 6]`

and `lt [7:10]`

respectively.
The value of the boundary index is the pivot.
If there are duplicate values, the value selected as the pivot may be in the sorted list.
The boundary index is sorted and the position is fixed.
The element whose position is fixed will be displayed as `Result`

.

Bottom Top | Result |
---|---|

`f(lt[7:10])` , `f(lt[0:6])` |
`lt[6]` |

Then `f (lt [0: 6])`

is pushed onto the call stack for execution.

Bottom | Top | Result |
---|---|---|

`f(lt[7:10])` |
`f(lt[0:6])` |
`lt[6]` |

Here, 1 is chosen as the pivot, with values less than 1 being split forward and values greater than 1 being split backward.
The delimiter index is 1, and `quickSort ()`

is executed on`lt [0: 1]`

and`lt [2: 6]`

, respectively.

Bottom | Top | Result |
---|---|---|

`f(lt[7:10])` |
`f(lt[2:6])` , `f(lt[0:1])` |
`lt[1]` + `lt[6]` |

`F (lt [0: 1])`

is pushed onto the call stack.

Bottom | Top | Result | |
---|---|---|---|

`f(lt[7:10])` |
`f(lt[2:6])` |
`f(lt[0:1])` |
`lt[1]` + `lt[6]` |

`lt [0: 1]`

has a length of 1, so it is positioned and popped from the call stack.

Bottom | Top | Result |
---|---|---|

`f(lt[7:10])` |
`f(lt[2:6])` |
`lt[0:2]` + `lt[6]` |

The call stack returns, then the range of `lt [2: 6]`

is sorted.
Here, 4 is chosen as the pivot and is divided into a range of values less than 4 and values greater than 4.
The delimiter index is 4, and `quickSort ()`

is executed on`lt [2: 4]`

and`lt [5: 6]`

, respectively.
Establish the position of `lt [4]`

.

Bottom | Top | Result |
---|---|---|

`f(lt[7:10])` |
`f(lt[5:6])` , `f(lt[2:4])` , |
`lt[0:2]` + `lt[4]` + `lt[6]` |

`F (lt [2: 4])`

is pushed onto the call stack.

Bottom | Top | Result | |
---|---|---|---|

`f(lt[7:10])` |
`f(lt[5:6])` |
`f(lt[2:4])` |
`lt[0:2]` + `lt[4]` + `lt[6]` |

2 is chosen as the pivot and is divided into less than 2 and greater than 2.
A delimiter index of 2 is used to execute `quickSort ()`

at `lt [2: 2]`

and `lt [3: 4]`

, respectively.
`lt [2]`

is confirmed.

Bottom | Top | Result | |
---|---|---|---|

`f(lt[7:10])` |
`f(lt[5:6])` |
`f(lt[3:4])` , `f(lt[2:2])` |
`lt[0:3]` + `lt[4]` + `lt[6]` |

Both `lt [2: 2]`

and `lt [3: 4]`

are executed, but the length of the range is 1 or less, so the position is fixed.
`f (lt [2: 2])`

is pushed and popped because it is 0 in length.
`f (lt [3: 4])`

is executed, the position of `lt [3]`

is fixed, and it is popped.

Bottom | Top | Result |
---|---|---|

`f(lt[7:10])` |
`f(lt[5:6])` |
`lt[0:3]` + `lt[4]` + `lt[6]` |

The call stack returns, then the range of `lt [5: 6]`

is sorted.
Since `lt [5: 6]`

also has a range of 1, the position is fixed and popped.
The first half of the list is now sorted and confirmed.
The second half is processed in the same way.

Bottom Top | Result |
---|---|

`f(lt[7:10])` |
`lt[0:7]` |

9 is chosen as the pivot and is divided into `lt [7: 9]`

and `lt [9: 9]`

.
`lt [9]`

is confirmed.

Bottom Top | Result |
---|---|

`f(lt[9:9])` , `f(lt[7:9])` |
`lt[0:7]` + `lt[9]` |

`f (lt [7: 9])`

is pushed.

Bottom | Top | Result |
---|---|---|

`f(lt[9:9])` |
`f(lt[7:9])` |
`lt[0:7]` + `lt[9]` |

8 is chosen as the pivot and is divided into `lt [7: 8]`

and `lt [8: 8]`

.
`lt [8]`

is confirmed.

Bottom | Top | Result |
---|---|---|

`f(lt[9:9])` |
`f(lt[8:8])` , `f(lt[7:8])` |
`lt[0:7]` + `lt[8:10]` |

`f (lt [7: 8])`

is pushed.

Bottom | Top | Result | |
---|---|---|---|

`f(lt[9:9])` |
`f(lt[8:8])` |
`f(lt[7:8])` |
`lt[0:7]` + `lt[8:10]` |

The position of `lt [7]`

is fixed.

Bottom | Top | Result |
---|---|---|

`f(lt[9:9])` |
`f(lt[8:8])` |
`lt` |

Both `lt [8: 8]`

and `lt [9: 9]`

have a length of 0, so they end without doing anything and the process ends.

Result |
---|

`lt` |

You can see that it is similar to the behavior of the call stack in the Fibonacci sequence.

Quicksort will also be converted to non-recursive. The process of being piled up on the call stack is piled up on the stack in the same way as the conventional way of thinking. In the case of quicksort, the range that must be sorted next is pushed onto the stack. The implementation looks like this: I thought it would be a pain, but now it's almost the same as the recursive version.

```
def quickSortL(lt):
length = len(lt)
stack = [(0, length - 1)]
while len(stack) > 0:
l, r = stack.pop()
if l >= r:
continue
i = l
j = r
p = getPivot(lt, l, r)
while i < j:
while lt[i] < p:
i += 1
while lt[j] > p:
j -= 1
if i < j:
if lt[i] == lt[j]:
j -= 1
else:
lt[i], lt[j] = lt[j], lt[i]
stack.append((j + 1, r))
stack.append((l, i - 1))
```

At this point, it's a slapstick, but I'd like to consider a 2-minute search.

First of all, it is a recursive version, but I implemented it as follows.
This assumes that you are passing a sorted list with unique values.
You can use ʻuniqueSorted ()`to create a list that meets the conditions. This also includes`

print ()` for explanation.

```
def uniqueSorted(lt):
return sorted(list(set(lt)))
def binarySearchR(lt, n):
return _binarySearchR(lt, n, 0, len(lt) - 1)
def _binarySearchR(lt, n, l, r):
if l > r:
return -1
middleIndex = int(l + (r - l) / 2)
middleValue = lt[middleIndex]
print(getListIndeces(lt[l:r + 1], l))
print(listToFormatedString(lt[l:r + 1]), middleIndex, middleValue)
if middleValue > n:
return _binarySearchR(lt, n, l, middleIndex - 1)
elif middleValue < n:
return _binarySearchR(lt, n, middleIndex + 1, r)
else:
return middleIndex
```

I ran it as follows:

```
lt = [3, 6, 12, 13, 14, 16, 17, 22, 51, 56, 58, 62, 66, 70, 74, 75, 80, 92, 94, 95]
n = 70
print(binarySearchR(lt, n))
```

Then, the following execution result will be obtained.

```
> 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19<
[ 3, 6, 12, 13, 14, 16, 17, 22, 51, 56, 58, 62, 66, 70, 74, 75, 80, 92, 94, 95] 9 56
>10, 11, 12, 13, 14, 15, 16, 17, 18, 19<
[58, 62, 66, 70, 74, 75, 80, 92, 94, 95] 14 74
>10, 11, 12, 13<
[58, 62, 66, 70] 11 62
>12, 13<
[66, 70] 12 66
>13<
[70] 13 70
13
```

Illustrates the call stack.
First, it is pushed onto the call stack with `lt`

as a list and 70 as the number you want to find.
9 is chosen as the median index.
The value of `lt [9]`

is 56, which is less than the number 70 you want to find.
Therefore, we will proceed with the search for the second half of the list.

Bottom Top | |
---|---|

`f(lt)` |

`BinarySearch ()`

is executed as `lt [10:20]`

to search the second half of the list.
`f (lt [10:20])`

is pushed.
14 is chosen as the median index.
The value of `lt [14]`

is 74, which is greater than the number 70 you want to find.
Therefore, we will proceed with the search for the first half of the list.

Bottom | Top |
---|---|

`f(lt)` |
`f(lt[10:20])` |

`BinarySearch ()`

is executed as `lt [10:14]`

to proceed with the search.
`f (lt [10:14])`

is pushed.
Index 11 is chosen.
The value of `lt [11]`

is 62, which is less than the number 70 you want to find.
Therefore, we will proceed with the search for the second half of the list.

Bottom | Top | |
---|---|---|

`f(lt)` |
`f(lt[10:20])` |
`f(lt[10:14])` |

`BinarySearch ()`

is executed as `lt [12:14]`

to proceed with the search.
`f (lt [12:14])`

is pushed.
Index 12 is chosen.
The value of `lt [12]`

is 66, which is less than the number 70 you want to find.
Therefore, we will proceed with the search for the second half of the list.

Bottom | Top | ||
---|---|---|---|

`f(lt)` |
`f(lt[10:20])` |
`f(lt[10:14])` |
`f(lt[12:14])` |

`BinarySearch ()`

is executed as `lt [13:14]`

to proceed with the search.
`f (lt [13:14])`

is pushed.
Index 13 is chosen.
The value of `lt [13]`

is 70, which is equal to the number 70 you want to find.
Since an equal number was found, it returns the index value of 13.

Bottom | Top | |||
---|---|---|---|---|

`f(lt)` |
`f(lt[10:20])` |
`f(lt[10:14])` |
`f(lt[12:14])` |
`f(lt[13:14])` |

Below, it is popped from the call stack while returning a value.

Bottom | Top | |||
---|---|---|---|---|

`f(lt)` |
`f(lt[10:20])` |
`f(lt[10:14])` |
`f(lt[12:14])` |
13 |

Bottom | Top | ||
---|---|---|---|

`f(lt)` |
`f(lt[10:20])` |
`f(lt[10:14])` |
13 |

Bottom | Top | |
---|---|---|

`f(lt)` |
`f(lt[10:20])` |
13 |

Bottom | Top |
---|---|

`f(lt)` |
13 |

Bottom Top |
---|

13 |

The movement of the call stack is now the same as factorial. It can be said that it has almost the same structure except for the difference in conditional branching and whether to process with the returned value.

The non-recursive version now looks like this: This is also the same as Quicksort, and it has almost the same structure as the recursive version.

```
def binarySearchL(lt, n):
stack = [(0, len(lt) - 1)]
while len(stack) > 0:
l, r = stack.pop()
if l > r:
return -1
middleIndex = int(l + (r - l) / 2)
middleValue = lt[middleIndex]
if middleValue > n:
stack.append((l, middleIndex - 1))
elif middleValue < n:
stack.append((middleIndex + 1, r))
else:
return middleIndex
```

In the case of a 2-minute search, the call stack is a simple movement that does not increase and decrease repeatedly, so it can be easily converted without using the stack. The following is a slightly simplified version.

```
def binarySearchL2(lt, n):
l, r = 0, len(lt) - 1
while l <= r:
middleIndex = int(l + (r - l) / 2)
middleValue = lt[middleIndex]
if middleValue > n:
l, r = l, middleIndex - 1
elif middleValue < n:
l, r = middleIndex + 1, r
else:
return middleIndex
return -1
```

Some recursive functions list only simple algorithms, but the call stack behavior is similar for all recursive functions. In other words, it can be said that it can be implemented with a similar structure. After all, I thought that I had a hard time converting to a non-recursive function because I didn't fully understand the structure of the recursive function. The big difference is whether you use the call stack or the stack. Then, I realized the importance of basic data structures and algorithms learned at school. The basics are important. Does it mean that the unscrupulous student days have come around (´ ・ ω ・ \ `)

You can check the call stack depth of `python`

with`sys.getrecursionlimit ()`

.
It depends on the environment, but you can change the depth with `sys.setrecursionlimit (limit)`

.

```
graph TB;
0[5]---1[3]
0---2[4]
1---3[1]
1---4[2]
4---5[0]
4---6[1]
2---7[2]
2---8[3]
7---9[0]
7---10[1]
8---11[1]
8---12[2]
12---13[0]
12---14[1]
```

Recommended Posts