How to Implement Recursive Functions

How to Implement Recursive Functions

Converting all loops into recursive functions is possible, but it's generally a challenging task. The reason behind this is that the mindset required for recursive functions can differ somewhat from the usual human thinking process. Therefore, acquiring this skill requires sufficient practice and familiarity.

To overcome this, I believe that organizing loops effectively is key. I've created the following table as a tool to help with this. Based on this table, I aim to gradually implement more complex loops as recursive functions, with the eventual goal of being able to implement them without relying on the table.

Recursive Function Implementation Table

• Objective:
• Termination Condition (Base Case):
• Do Previous Results Matter?:
• Problem Division (Divide the Problem):
• Combining Results:
• Recursive Call, Modifications Before Moving to the Next Step:

Practice Examples

Reverse a String Recursive Function Implementation Table

• Objective: Reverse a string

• Termination Condition (Base Case): When there are no more characters to reverse (i.e., when the length of the string becomes 0)

  if len(s) == 0: return s
  

• Do Previous Results Matter?: Yes, each recursive call reverses the remaining part of the string

• Problem Division (Divide the Problem): Reversing the rest of the string, excluding the first character

  string - s[-1]
  

• Combining Results:

  stringbuilder sb.append s[-1]
  

• Recursive Call, Modifications Before Moving to the Next Step: Concatenate the current character to the end of the reversed remaining string from the recursive call

  return reverse_string(s[1:], sb)
  

Completed Code

public static String reverseString(String input, StringBuilder sb){

        if(input.length()==0) return sb.toString();

        sb.append(input.charAt(input.length()-1));
        return reverseString(input.substring(0, input.length()-1),sb);
}

Factorial Recursive Function Implementation Table

• Objective: Calculate factorial

• Termination Condition (Base Case):

  if n == 0 or n == 1:
          return 1
  

• Do Previous Results Matter?: Yes

• Problem Division (Divide the Problem):

  factorial(input-1) * input
  

• Combining Results:

  factorial(input-1) * input
  

• Recursive Call, Modifications Before Moving to the Next Step:

  input-1
  

Completed Code

public static int factorial(int n) {
        if (n <= 1) {
            return 1;
        }
        return n * factorial(n - 1);
}

improve

public static int factorial(int n) {
        return factorialRecur(n, 1);
}

private static int factorialRecur(int n, int result) {
        if (n <= 1) {
            return result;
        }
        return factorialRecur(n - 1, n * result);
}