INB221 Lecture Notes - Lecture 6: Merge Sort, Substring, Quicksort
4 Jul 2013
School
Department
Course
Professor
Document Summary
Recursion involves reducing a large problem to smaller problems of the same form. If we"ve been tasked with distributing 1000000 pieces of junk mail, you couldn"t possibly doing it yourself. You could use a pyramid scheme, which lets people distribute to other people, and it keeps going down the chain. Having a function call itself is the principle behind recursion. A simple factorial mathematical function to multiply numbers from 1 to n. you could do it iteratively (in a for loop). Anything done iteratively can most likely be doing with recursion. If n = 0, the factorial function will return 1, and if it"s not zero, it will call itself until n reaches 0. Every time the function is called, a new stack frame is created, and any local variables and parameters that are defined in our main function is placed in the stack frame.
