10.1: Understand Recursive Functions
- Page ID
- 128202
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\( \newcommand{\dsum}{\displaystyle\sum\limits} \)
\( \newcommand{\dint}{\displaystyle\int\limits} \)
\( \newcommand{\dlim}{\displaystyle\lim\limits} \)
\( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)
( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\id}{\mathrm{id}}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\kernel}{\mathrm{null}\,}\)
\( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\)
\( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\)
\( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\(\newcommand{\longvect}{\overrightarrow}\)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)A recursive function in C++ or other programming languages is a function that calls itself to form a recursion, which is an extremely powerful problem-solving technique. Problem that at first appear to be quite difficult often have a simple recursive solution.
Like other problem-solving technique, recursion breaks a problem into several smaller problems. But the difference about recursion is that those smaller problems are exactly the same type as the original problem, thus, the way to solve those smaller problem is going to be the same as the way to solve the original problem. And also, those smaller problems are themselves breaking into even smaller problems of the same type.
For example, if we want to find the largest number in a set of 5 numbers, we can break this problem into following smaller problems:
- Find the largest in a set of 4 of those 5 numbers
- Find the larger number between the largest number we found in those 4 numbers and the other number in the original set, the result will be the largest number of those five numbers in the original set
And the problem "Find the largest in a set of 4 of those 5 numbers can be further broken down to two even smaller problem
- Find the largest in a set of 3 of those 4 numbers
- Find the larger number between the largest number we found in those 3 numbers and the other number in the 4-number set, the result will be the largest number of those 4 numbers
We can continue this:
- Find the largest in a set of 2 of those 3 numbers
- Find the larger number between the largest number we found in those 2 numbers and the other number in the 3-number set, the result will be the largest number of those 3 numbers
and
- Find the largest in a set of 1 of those 2 numbers
- Find the larger number between the largest number we found in those 1 numbers and the other number in the 2-number set, the result will be the largest number of those 2 numbers
Since the largest number in a set of 1 number is the number itself, we have had the solution of the last problem. Then we pass the solution to the previous problem and we can easily find the largest number in a 2-number set by comparing two numbers
Continue to pass the largest number found in the 2-number set to the problem with 3-number set, we can also find the largest number in the 3-number set by comparing two numbers (one is the largest number in the 2-number set and the other one is the third number in the 3-number set.
Continue to pass the largest number found in the 3-number set to the problem with 4-number set, we can also find the largest number in the 4-number set by comparing two numbers (one is the largest number in the 3-number set and the other one is the fourth number in the 4-number set.
Continue to pass the largest number found in the 4-number set to the problem with 5-number set, we can also find the largest number in the 5-number set by comparing two numbers (one is the largest number in the 4-number set and the other one is the fifth number in the 5-number set. And this is solution of the original problem.
If you feel very confusing about the recursive technique we used in solving this problem, let me help you to understand it with following scenario:
Assume you have four brothers and sisters, they are age 15, 10, 8, and 5. Now, you got five boxes with different numbers of candies in each box. You would like to find out which box that has the most candies in it.
Of course, you can do the job all by yourself by opening each boxes and count the candies in the each box. But, you don't want to do it all by yourself, you would like to ask your brothers and sisters to help you out.
You keep one box of candies and do the counting for this box and pass the rest of four boxes to your 15-year old brother and let him to find out which box that contains the most of candies in those four boxes.
Your 15-years old brother can do the job by himself by opening those four boxes and count the candies in each box, but he doesn't want to either, he, like you, would like to ask the rest of brothers and sisters for help
He keep one box of candies and do the counting and pass the rest of three boxes to his 10-years old sister and let her to find out which box that contains the most candies.
Again, the 10-years old sister keeps only one box and do the counting and pass the rest of two boxes to her 8-years old brother and let him to find out which box that has the most candies.
Now, 8-years old brother also just keep one box for counting and pass the other box to his 5-years old sister and let her to find out which box that has the most candies.
The 5-years old sister doesn't need to do anything to find out which box has the most candies because she only has one box. But she is a nice girl, she still count the number of candies in the box and tell the her 8-year brother: this box has the most candies and the number of the candies in this box is so on so.
The 8-years old brother got the answer from 5-years old sister and compare the number got from his sister with the number in his hand, pass the box that has more candies along with the number of candies in the box to his 10-years old sister
The 10-years old sister got the answer from 8-years old brother and compare the number got from her younger brother with the number in his hand, pass the box that has more candies along with the number of candies in the box to her 15-years old brother.
The 15-years old brother got the answer from 10-years old sister and compare the number got from his sister with the number in his hand, pass the box that has more candies along with the number of candies in the box to you
Now, all you need to do is comparing the number in your hand with the number on the box you receive from your 15-years old brother, you will be easily find out the box that contains the most candies in those five boxes you receive originally.
The original job was broken into five smaller jobs. Each of those smaller jobs only needs to conducting a single box counting and a single comparison except the job that passed to the youngest sister.
The way we solve this candy counting problem is called recursion. We break a bigger problem into five smaller and easier problems of the same type.
However, understanding recursion is one thing and being able to use this technique in coding this another thing.