recursion

• RECURSION

  process where a function calls itself
• RECURSION

  capability to save the condition it was in or the particular process it was serving when calling itself
• KEY COMPONENTS OF RECURSION

  1. base case
  2. recursive case
• Base Case

  • a condition that stops the recursion
• Recursive Case

  the part of the function where it calls itself.
• ITERATION

  process where a set of instructions is repeatedly executed using loops (for, while, do-while) until a condition is met.
• characteristics

  A) high (stack frames)

  B) faster

  C) simplex for complex problems

  D) low

  E) slower (function calls)

  F) can be harder to implement

  G) tree-traversal, divide-and-conquer algorithm

  H) loops, simple repetitive tasks

  
• when to use recursion

  when dealing with problems naturally defined in terms of smaller subproblems.
• when to use recursion

  ex Fibonacci, tree traversal, backtracking prob
• when to use iteration

  when efficiency is critical and the problem can be easily solved using loops.
• RECURSIVE MUST HAVE

  • Base case - the condition that allows the algorithm to stop recurring.
  • Change its state and move toward the base case. A change of state means that some data that the algo is using is modified.
  • Call itself, recursively.
• Stack overflow

  an infinite recursion that might cause the program to run out of memory and may result in crashing. no proper way of stopping the condition.
• 2 CLASSES OF RECURSION

  1. direct recursion
  2. indirect recursion
• Direct Recursion

  when a method directly calls itself.
• Indirect Recursion

  occurs when a method calls another method, eventually calling the original method.
• • Linear recursion
  • Tail recursion
  • Binary recursion
  • Mutual recursion
• linear recursion

  only makes a single call to itself each time the function runs.
• linear recursion

  reducing the problem size by a constant amount each time.
• tail recursion

  the recursive call is the last statement that is executed by the function
• binary recursion

  which calls itself twice during the course of its function
• binary recursion

  It is used when a problem can be divided into two subproblems
• mutual recursion

  when a recursive procedure is divided among two functions that call each other.
• mutual recursion

  used when solving a problem requires alternating between different functions
• loop

  cause a section of your program to be repeated a certain number of times
• loop

  repeats until the condition remains true.
• loop

  terminates when the condition becomes false
• TYPES OF LOOP

  1. While loop
  2. Do while loop
  3. For loop
• While Statement syntax:

  while ( condition )

  statement;
• While Statement

  if the condition is true, the statement is executed. then the condition is evaluated again, and if it is still true, the statement is executed again
• While Statement

  the statement is executed repeatedly until the condition becomes false.
• DO WHILE LOOP syntax:

  do{

  }

  while (condition);
• do while loop

  The body of the do.. while is executed once before the condition is checked
• do while loop

  print before validate
• FOR LOOP syntax:

  for (initilization; condition; update) {

  / / body of-loop

  }
• output:

  0

  1

  2

  3

  4

  5


  for(int i = 0; i<=5++)

  {

  cout << i <<endl;

  }