📂Algorithm

Reasons to Be Careful When Using Recursive Functions

Caution

When you first learn programming, regardless of the language, there’s a common caution that ‘recursion should be used carefully.’ This is because recursion isn’t as frequently utilized technique, and the reason behind this caution is often left unexplained. This can lead to confusion for learners on why such a useful method is discouraged. Let’s delve into the examples to understand it better.

Example

def fibo1(n) :
    if n==1 or n==2 :
        return 1
    else :
        return fibo1(n-1) + fibo1(n-2)
 
for i in range(1,11) :
    print(fibo1(i))

Recursive function calls provide a simple yet elegant solution to various problems encountered in programming. It’s advantageous to write and read such code, as it generally simplifies potentially complicated code. For instance, if you need to write a program returning the Fibonacci sequence, implementing it with a recursive function could simplify your task. Executing Python code like the above would calculate the Fibonacci sequence up to the $10$th term as shown:

However, this method, while convenient for us, is quite impractical for a computer to process. Computers perform the calculation return fibo1(n-1) + fibo1(n-2) each time it’s called, not understanding the recursion formula $$ a_{n} : = \begin{cases} 1 &, n \le 2 \\ a_{n-2} + a_{n-1} &, n \ge 3 \end{cases} $$ . Even if previous terms are stored somewhere in memory, what the programmer has asked through a recursive function isn’t to ‘refer to the previous term’ but to ‘calculate the previous term.’ The following is a modified version of the function that alerts each time it’s called, and the process of calculating $a_{10}$ is shown in a gif:

For $a_{10}$ to be calculated, $a_{8}$ and $a_{9}$ need to be evaluated. But, for $a_{9}$ to be evaluated, $a_{7}$ and $a_{8}$ are necessary. This clearly shows that for $a_{10}$ to be called, $a_{8}$ must be called at least twice. Here is a display of how many times each fibo(n) is called to calculate fibo(10):

fibo(n)	Count
fibo(9)	1
fibo(8)	2
fibo(7)	3
fibo(6)	5
fibo(5)	8
fibo(4)	13
fibo(3)	21

Interestingly, the redundant calls when calculating the Fibonacci sequence increase following the Fibonacci sequence itself. Such redundancy results in a significant waste of memory and time. Moreover, given that the essence of recursion is ‘repetition,’ this issue inevitably accompanies recursion.

To circumvent these problems, a method known as dynamic programming exists. However, this method is practically tantamount to not using recursion at all. Dynamic programming is not a solution to the issues of recursive calls but an alternative to recursion, understood precisely when you grasp why recursion should be avoided.

Code

import time
 
def fibo1(n) :
    if n==1 or n==2 :
        return 1
    else :
        return fibo1(n-1) + fibo1(n-2)
 
for i in range(1,11) :
    print(fibo1(i))
 
def fibo(n) :
    if n==1 or n==2 :
        return 1
    else :
        print("fibo(",n,") 호출됨!")
        return fibo(n-1) + fibo(n-2)
 
for i in range(1,11) :
    print(fibo1(i))
 
print(fibo(10))

See Also

• Laplace Expansion