0) Recursion

A recursive function is a function that calls itself. When utilizing a recursive function, need a base case which is a condition to stop recalling the function. Whenever you make a recursive call you want to adjust the parameter to move closer to the base case.

Be sure to consider what inputs you give your recursive function and what you will return.

1) Sum of first n natural numbers

Given a number n, find the sum of the first n natural numbers. To calculate the sum, we will use a recursive function recur_sum().

Input : 3
Output : 6
Explanation : 1 + 2 + 3 = 6

Input : 5
Output : 15
Explanation : 1 + 2 + 3 + 4 + 5 = 15

2) First Uppercase Letter

Given a string, find its first uppercase letter.

Input : geeksforgeeKs
Output : K

Input  : geekS
Output : S

3) Reverse String

Given a string, return its reverse string counterpart.

Input: “Welcome to PANDA”
Output: “ADNAP ot emocleW”

4) Fibonacci

The Fibonacci numbers, commonly denoted F(n), form a sequence called the Fibonacci sequence. Each number in this sequence is the sum of the two preceding ones, starting from 0 and 1.

Input: 2
Output: 1
Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.

Input: 3
Output: 2
Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.

Recursive:
     Time: O(2^n)
     Space: O(n)
Iterative Array:
     Time: O(n)
     Extra: O(n)
Iterative Variable:
     Time: O(n)
     Extra: O(1)
Mathematical:
     Time: O(1)
     Extra: O(1)

Trial Problems

public class LinkedList<T>{
     private class LinkedNode<T>{
          private T item;
          private LinkedNode<T> next;

          private LinkedNode(T item){
               this.item = item;
               this.next = null;
          }   

          private LinkedNode(T item, LinkedNode<T> next){
               this.item = item;
               this.next = next;
          }   
     }

     private int size = 0;
     private LinkedNode<T> head;

     public LinkedList(){
          this.head = null;
     }

     public LinkedList(T[] arr){
          this.head = null;
          for (int i = 0; i < arr.length; i++){
               addAtEnd(arr[i]);
          }
     }

     public boolean addAtEnd(T item){
          if (size == 0){
               head = new LinkedNode<T>(item);
               size++;
               return true;
          }

          LinkedNode<T> curr = head;
          for (int i = 0; i < size; i++){
               curr = curr.next;
          }

          curr.next = new LinkedNode<T>(item);
          size++;
          return true;
     }

     //TODO
     public void reverseLL(){

     }
}

1) Recursive Reverse Linked List

Utilizing the LinkedList class definition above, implement the reverseLL function that reverses the Linked List. You may create additional functions and modify the base function.

Input: [0] → [1] → [2]

Output: [2] → [1] → [0]

2) Recursive Merge Sorted Linked Lists

Merge two sorted linked lists and return it as a new sorted list.

Input: 
l1 = [1] -> [2] -> [4] 
l2 = [1] -> [3] -> [4]
Output: [1] -> [1] -> [2] -> [3] ->[4] ->[4]

Input: 
l1 = [1] -> [3] -> [4] ->[6]
l2 = [2] -> [5] -> [6]
Output: [1] -> [2] -> [3] -> [4] -> [5] -> [6] -> [6]

Note: Maybe it is a little easier using recursion? Be mindful of what inputs you use and what you return