Revise Recursion

[emmcold]

Whenever revising recursion remember to answer these questions:

1. What is recursion? - Any function that calls itself is called recursive. A recursive method solves a problem by calling a copy of itself to work on a smaller problem. This is called the recursion step. It is important to ensure that the recursion stops.
2. How does a recursion look like? functionName(parameters){ base case (stoping condition). functionName(parameters--usually change). }
3. Why recursion?- Recursion is useful technique borrowed by mathematics, where the code is generally shorter and easier to write than iterative code. Recursion is MOST useful for tasks that can be defined in terms of similar smaller substasks. i.e. sort, search and traversal often have recursive solution.
4. How will you explain recursion to a kid? - @sinhaaman can you help with this?
5. Example of recursion: - Factorial n!=1 if n=0, n!=n*(n-1)! if n>0.
6. Show how recursion works in memory - function call stack and show visual representation, in case of trees, it is an actual tree.
7. Which way is better? Iteration or recursion? - Depends on what we are trying to achieve. Some differences: Recursion- Terminates when a base case is reached. - Each recursive call requires extra space in the function call stack in memory. -If we run in infinite recursion we run into stack overflow. - Solutions to some problems are easier to formulate with recursion. Iteration- Terminates when a condition is false. Each iteration does require extra space. - An infite loop could loop forever since there is no extra memory (no stack overflow).

Typical problems of recursion:

• Factorial, Fibonacci series
• Merge Sort, Quick sort
• Binary Search
• Tree traersals and many tree problems: inorder, preorder, postorder
• Graph Traversals: DFS(Depth First Search) and BFS(Breadth First Search)
• Dynamic Programming Examples
• Divide and conquer algorithms
• Towers of Hanoi
• Backtracking algorithms.

[sinhaaman]

Q. How will you explain recursion to a kid? A. Ask a kid to climb to the staircase until you say stop. This stop keyword is the base case of recursion. While coming down or going up ask the child to count the number of the stairs. This is the activity which one performs in the recursive code. The child ends up in the starting position since he/she has to come down. This shows that the stack in recursion is cleared once the function call is ends.

[sinhaaman]

This is a very well compiled list about recursion!! Kudos 👍 Good Job 🥇