Consider a conversion from a Python recursive function to a non-recursive function

Introduction

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.

Assumed reader

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.

Call stack and stack

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.

Why recursive functions can be avoided

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.

Conversion policy

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.

Factorial

First, consider a simple factorial as an example.

Factorial recursive version

Implementing factorial using recursion gives:

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

Factorial recursive call stack movement

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 to5 * factorialR (4)when executed.

It then calls factorialR (4) and pushes it onto the call stack. factorialR (4) is converted to4 * factorialR (3)when executed.

Hereafter, it works in the same way.

The recursive call continued until n = 0.

If n = 0, 1 is returned.

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.

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.

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.

Factorial 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.

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.

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.

Hereafter, it works in the same way.

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

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

Factorial non-recursive version part 2

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.

When n = 0, it is 0! = 1, so 1 is fixed.

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

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.

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

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

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

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

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

Factorial non-recursive simplification

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)

Fibonacci sequence

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

Fibonacci sequence recursive version

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)

Fibonacci sequence recursive call stack behavior

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).

Then fibonacciR (3) is called and pushed onto the call stack. When executed, it will be converted to fibonacciR (1) + fibonacciR (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).

To resolve fibonacciR (2), it is called and pushed onto the call stack. When executed, it will be converted to fibonacciR (0) + fibonacciR (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).

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.

1 + fibonacciR (1) when calling fibonacciR (3) is resolved to 1 + 1 = 2.

Part of fibonacciR (3) + fibonacciR (4) when calling fibonacciR (5) is resolved to become 2 + fibonacciR (4).

It works in the same way below.

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.

Fibonacci sequence recursive binary version

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.

Fibonacci sequence 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.

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.

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

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.

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

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.

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.

Hereafter, it works in the same way.

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)

Fibonacci sequence non-recursive version simplification

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

Quick sort

Next, consider quicksort.

Quicksort recursive version

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 Recursive call stack behavior

Quicksort also illustrates the movement of the call stack. First, it is pushed to the call stack as 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.

Then f (lt [0: 6]) is pushed onto the call stack for execution.

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 onlt [0: 1]andlt [2: 6], respectively.

F (lt [0: 1]) is pushed onto the call stack.

lt [0: 1] has a length of 1, so it is positioned and popped from the call stack.

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 onlt [2: 4]andlt [5: 6], respectively. Establish the position of lt [4].

F (lt [2: 4]) is pushed onto the call stack.

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.

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.

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.

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

f (lt [7: 9]) is pushed.

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

f (lt [7: 8]) is pushed.

The position of lt [7] is fixed.

Both lt [8: 8] and lt [9: 9] have a length of 0, so they end without doing anything and the process ends.

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

Quicksort non-recursive version

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))

2-minute search

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

2-minute search recursive version

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 includesprint ()` 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

2-minute search Recursive call stack behavior

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.

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.

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.

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.

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.

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

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.

2-minute search non-recursive version

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

Finally

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 (´ ・ ω ・ \ `)

appendix

Check / change the depth of the call stack.

You can check the call stack depth of python withsys.getrecursionlimit (). It depends on the environment, but you can change the depth with sys.setrecursionlimit (limit).

Binary mermaid

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]