Create FREE 'HowTo' Videos with MyGuide

Recursion



Pass Quiz and Get a Badge of Learning



Content "filtered", Please subscribe for FULL access.


Chapter 8 : Recursion


Recursion arrow_upward


  • Recursion is a method of solving problems that involves breaking a problem down into smaller and smaller sub-problems until you get to a small enough problem that it can be solved trivially.
  • Usually recursion involves a function calling itself. While it may not seem like much on the surface, recursion allows us to write elegant solutions to problems that may otherwise be very difficult to program.
  • Recursion is an alternative to iteration (loop):
    • Often more "elegant” and concise than a loop.
    • Sometimes very inefficient.
  • Recursion should be considered when:
    • A problem can be defined in terms of successive smaller problems of the same type, i.e. recursively.
    • Eventually the problem gets small enough that the answer is known (base case).
    • Reducing the problem size leads to the base case.
  • Sometimes the "work" of the algorithm is done after the base case is reached.

  • The Three Laws of Recursion arrow_upward


  • All recursive algorithms must obey three important laws:
    • A recursive algorithm must have a base case.
    • A recursive algorithm must change its state and move toward the base case.
    • A recursive algorithm must call itself, recursively.

    Base Case

    if (answer is known) provide the answer.

    Recursive Case

    make a recursive call to solve a smaller version of the same problem


    Direct Recursion arrow_upward


  • A function calls by itself is known as direct recursion.

  • Indirect Recursion arrow_upward


  • Indirect Recursion is when a function calls a second function which in turn calls the first function.

  • Recursive Definitions                arrow_upward


  • A recursive formula always uses the preceding term to define the next term of the sequence.
  • N!, for any positive integer N, is defined to be the product of all integers between 1 and N inclusive.
  • This definition can be expressed recursively as:
  •      1!  =  1

         N!  = N * (N-1)!

  • The concept of the factorial is defined in terms of another factorial.
  • Eventually, the base case of 1! is reached.

  • Cases in Recursion arrow_upward


    Base case:

  • A case in recursion, in which the answer is known when the termination for a recursive condition is to unwind back.

  • Recursive Case:

  • A case which returns to the answer which is closer.

  • Run-time Stack:

  • A run time stack used for saving the frame stack of a function when every recursion or every call occurs.

  • Tail Recursion:

  • It is a situation where a single recursive call is consisted by a function, and it is the final statement to be executed. It can be replaced by iteration.

  • Thank You from Kimavi arrow_upward


  • Please email us at Admin@Kimavi.com and help us improve this tutorial.


  • Mark as Complete => Receive a Certificate in Data-Structure


    Kimavi Logo

    Terms and conditions, privacy and cookie policy | Facebook | YouTube | TheCodex.Me | Email Kimavi


    Kimavi - A Video Learning Library { Learning is Earning }

    Get Ad Free Learning with Progress Report, Tutor Help, and Certificate of Learning for only $10 a month



    All videos on this site created using MyGuide.

    Create FREE HowTo videos with MyGuide.