Recursive Function (재귀 함수)

Intro

Recursive Function usually helps beginners of Computer Science to further understand basic algorithms and also develop their 'computer-science-thinking skills'. It is to hereby note that recursive function is not an efficient type of algorithm!

Definition of Recursive Function

When something 'recurs', it occurs again. In other words, it is repeated until it qualifies a 'criteria'(base case) set up.

For example, a matryoshka doll is a common cliche in explaining recursive function, as shown below.

Photo by Wiem Zine from Medium

Thus a recursive function is an algorithm where it solves the same problem of a smaller scale, or the previous step, to solve a problem. That is why the function is called 'recursive', because it executes itself again.

Reucursive functions are very easy to write and are short, once you get used to the method. Yet it is not efficient, so there is no need to overuse this method.

Examples of Recursive function

1. Gausian Calculus(가우스의 계산법)

n = int(input())

def gaussian(n):
  if n == 1:
    return 1 # base case
  else:
    return n + gaussian(n-1)
  
print(gaussian(n))

2. Factorial

def factorial(n):
  if n == 1:
    return 1 # base case
  else:
    return n*factorial(n-1)

3. Checking palindrome

n = input()
def palindrome(n):
  if len(n) < 2:
    return True # base case
  if n[0] == n[-1]:
    return palindrome(n[1:-1])
  else:
    return False

print(palindrome(n))

4. Fibonacci Sequence

n = int(input())

def Fibonacci(n):
  if n == 0:
    return 0 # base case
  elif n == 1:
    return 1 # base case
  else:
    return Fibonacci(n-1) + Fibonacci(n-2)

print(Fibonacci(n))

5. Hanoian Tower

def TowerOfHanoi(n , s_pole, d_pole, i_pole):           
    if n == 1:
        print("Move disc 1 from pole",s_pole,"to pole",d_pole) # base case
        return
    TowerOfHanoi(n-1, s_pole, i_pole, d_pole)
    print("Move disc",n,"from pole",s_pole,"to pole",d_pole)
    TowerOfHanoi(n-1, i_pole, d_pole, s_pole)
 
n = 3
TowerOfHanoi(n, 'A', 'C', 'B')
# A, C, B are the name of poles

(Source: AskPython)

Conclusion

These were the explanations and examples of the algorithm, 'recursive function'. If you liked it, please click on the heart and share this. And ...

Image by Ksenia Samorukova from Dreamstime