# Recursion day 1

# Principle of Recursion

- A simple
`base case`

(or cases) — a terminating scenario that does not use recursion to produce an answer. - A set of rules, also known as
`recurrence relation`

that reduces all other cases towards the base case.

344. Reverse String

https://leetcode.com/problems/reverse-string/

Write a function that reverses a string. The input string is given as an array of characters `char[]`

.

Do not allocate extra space for another array, you must do this by **modifying the input array ****in-place** with O(1) extra memory.

You may assume all the characters consist of printable ascii characters.

**Example 1:**

**Input: **["h","e","l","l","o"]

**Output: **["o","l","l","e","h"]

**Example 2:**

**Input: **["H","a","n","n","a","h"]

**Output: **["h","a","n","n","a","H"]

**24. Swap Nodes in Pairs**

https://leetcode.com/problems/swap-nodes-in-pairs

Given a linked list, swap every two adjacent nodes and return its head.

You may **not** modify the values in the list’s nodes. Only nodes itself may be changed.

**Example 1:**

**Input:** head = [1,2,3,4]

**Output:** [2,1,4,3]

**Example 2:**

**Input:** head = []

**Output:** []

**Example 3:**

**Input:** head = [1]

**Output:** [1]

**Constraints:**

- The number of nodes in the list is in the range
`[0, 100]`

. `0 <= Node.val <= 100`

**Practice how to convert For Loop to RECURSION**

**Sum- **make a sum of string composed with numbers

ex. ‘123’

# Recurrence Relation

`recurrence relation`

: the relationship between the result of a problem and the result of its subproblems.`base case`

: the case where one can compute the answer directly without any further recursion calls. Sometimes, the base cases are also called*bottom cases*, since they are often the cases where the problem has been reduced to the minimal scale,*i.e.*the bottom, if we consider that dividing the problem into subproblems is in a top-down manner.

**206. Reverse Linked List**

https://leetcode.com/problems/reverse-linked-list/

Reverse a singly linked list.

**Example:**

**Input:** 1->2->3->4->5->NULL

**Output:** 5->4->3->2->1->NULL

**Follow up:**

A linked list can be reversed either iteratively or recursively. Could you implement both?

reference: https://www.geeksforgeeks.org/reverse-a-linked-list/