1. Recursive functions                                           【 Recursive function 】

---

• A recursive function is a function that calls itself directly or indirectly
• Related to recursive problem solving: binary tree traversal (divide & conquer)
• The function knows how to solve a base case (stopping rule)
• A recursion step is needed to divide the problem into sub-problems (key step)
• Need to check for termination

2. Factorial function                                               【 Factorial function 】

---

2.1. Design

2.1.1. Base Case

• Number = 0 || Number = 1 
• Result = 1

2.1.2. Recursive step

• Number > 1
• Result = Number x (Number - 1)!

2.2. Java Code

2.2.1.Java Code

• import java.util.Scanner;
  
  public class Factorial {
      public static void main(String[] args) {
          Scanner kb =new Scanner(System.in);
          System.out.println("Enter the number");
          int input = kb.nextInt();
          System.out.println("Result"+factorial(input));
      }
  
      public static int factorial(int input){
          //input
          if (input<0){
              return -1;
          }
          else if (input==0 ||input ==1){
              return 1;
          }else {
              return input*factorial(input-1);
          }
      }
  }

---

3. Fibonacci function                                      【 Fibonacci array 】

---

3.1. Design

3.1.1. Base Case

• fibonacci(0) = 0
• fibonacci(1) = 1 

3.1.2. Recursive step

• fibonacci(n) = fibonacci(n-1) + fibonacci(n-2)

3.1.3. How does it works?

• 

3.2. Java Code

3.2.1.Java Code

• import java.util.Scanner;
  
  public class Fibonacci {
      public static void main(String[] args) {
          Scanner kb =new Scanner(System.in);
          System.out.println("Enter the number");
          int input = kb.nextInt();
          System.out.println("Result: "+fibonacci(input));
      }
  
      public static int fibonacci(int input){
          if (input<0){
              return -1;
          }
          else if (input == 0){
              return 0;
          }
          else if (input ==1){
              return 1;
          }
          else {
              return fibonacci(input-1)+fibonacci(input-2);
          }
      }
  }

---

4. Recursion vs iteration

---

4.1. Recursion vs iteration

4.1.1. Use

• Iteration uses an iterative structure, while \ for
• Recursion uses a selection structure & function calls

4.1.2. Termination test

• Iteration ends when the continuation condition fails
• Recursion ends when a base case recognized

4.1.3. Features

• Iteration
  • Efficient but not easy to design
• Recursion
  • Slow (cost memory & processor power) but elegant

4.1.4. Info

• Every recursive function can be rewritten as an iterative function

---

5. Q & A

---

• What is the key step in designing a recursive function?
  • A recursion step is needed to divide the problem into sub-problems
• Every recursive function can be rewritten as an iterative function. (T or F)
  • T