Recursive function to sort an array [closed]

Question

I'm having trouble building a recursive function that sorts an integer array. At this point, I don't know any sorting algorithms, this is only my second CS course. I've seen a lot of solutions on here, but the issue with those solutions is that they have loops or nested conditions statements. In this function I cannot use loops or nested if statements, only single if/else statements.

I know you guys don't want to simply give answers since it takes away from the learning experience, but if I could just get pointed in the right direction I would greatly appreciate it.

Answer 1

To write a recursive function-

1. Write a function signature and assume that it will do your job with some magic.

2. Now think about base condition i.e what will your function do in case of smallest valid input.

3. Now write the induction step in which you call the same function on smaller input(generally).

   def sorting(arr):
   
       #Base Condition
       if len(arr) == 1:
           return
   
       #Induction
       last_num = arr[-1]
       arr.pop()
       sorting(arr)
       insert(arr, last_num)
   
       return arr
   
   def insert(arr, last_num):
   
       #Base Condition
       if len(arr) == 0 or arr[-1] <= last_num:
           arr.append(last_num)
           return
   
       #Induction
       val = arr[-1]
       arr.pop()
       insert(arr, last_num)
       arr.append(val)