MediaWiki API result

{
    "batchcomplete": "",
    "continue": {
        "gapcontinue": "Tests_-_Syntax",
        "continue": "gapcontinue||"
    },
    "warnings": {
        "main": {
            "*": "Subscribe to the mediawiki-api-announce mailing list at <https://lists.wikimedia.org/postorius/lists/mediawiki-api-announce.lists.wikimedia.org/> for notice of API deprecations and breaking changes."
        },
        "revisions": {
            "*": "Because \"rvslots\" was not specified, a legacy format has been used for the output. This format is deprecated, and in the future the new format will always be used."
        }
    },
    "query": {
        "pages": {
            "7": {
                "pageid": 7,
                "ns": 0,
                "title": "Recursive Functions",
                "revisions": [
                    {
                        "contentformat": "text/x-wiki",
                        "contentmodel": "wikitext",
                        "*": "A definition that defines an object in terms of itself is said to be ''recursive''.  In computer science, recursion refers to a function or subroutine that calls itself, and it is\na fundamental paradigm in programming. A recursive program is used for solving problems that can be broken down into sub-problems of the same type, doing so until\nthe problem is easy enough to solve directly.\n\n== Examples ==\n\n=== Fibonacci Numbers ===\n \nA common recursive function that you\u2019ve probably encountered is the Fibonacci numbers: 0, 1, 1, 2, 3, 5, 8, 13, and so on. That is, you get the next Fibonacci number by adding together the previous two. Mathematically, this is written as \n\n$$f(N)=f(N-1)+f(N-2)$$\n\nTry finding f(10). No doubt, you have the correct answer, because you intuitively stopped when you reach $f(1)$ and $f(0)$. \nTo be formal about this, we need to define when the recursion stops, called the ''base cases''. \nThe base cases for the Fibonacci function is $f(0)=0$, and $f(1)=1$. The typical way to write this function is as follows:\n$$f(N)=\\cases{N & if $N \\le 1$\\cr\nf(N-1)+f(N-2) & if $N > 1$}$$\n\nHere is a Python implementation of the Fibonacci function:\n\n::<syntaxhighlight lang=\"python\">\ndef Fibonacci(x):\n\u00a0 if (x <= 1) return x\n\u00a0 return Fibonacci(x-1) + Fibonacci(x-2)\n</syntaxhighlight>\n\n(As a challenge to the reader: How could you implement the Fibonacci function without using recursion?)\n\n=== Factorial Function ===\n\nConsider the factorial function, $n! = n * (n-1) * ... * 1$, with 0! defined as having a value of 1. We can define this recursively as follows: \n\n$$f(x)=\\cases\n{1 & if $x=0$\\cr\nx*f(x-1) & if $x\\gt 0$\\cr\n}$$\n\nWith this definition, the factorial of every non-negative integer can be found. \n\nHere is a Python implementation of the factorial function:\n::<syntaxhighlight lang=\"python\">def Factorial(x):\n\u00a0 if (x == 0) return 1\n\u00a0 return x * Factorial(x-1)\n</syntaxhighlight>\n\n=== Some Definitions ===\n\nA few definitions: ''Indirection recursion'' is when a function calls another function which eventually calls the original function. For example, A calls B, and then, before function B exits, function A is called (either by B or by a function that B calls). ''Single recursion'' is recursion with a single reference to itself, such as the factorial example above. ''Multiple recursion'', illustrated by the Fibonacci number function, is when a function has multiple self references. ''Infinite recursion'' is a recursive function that never returns because it keeps calling itself. The program will eventually crash with an ''out of memory'' error message of some sort. \n\nThis ACSL category focuses on mathematical recursive functions rather than programming algorithms.  While many mathematical functions can be done iteratively more efficiently than they can be done recursively, many algorithms in computer science must be written recursively.  The Tower of Hanoi which is referred to in one of the videos is a good example of this.  Another example is given in the sample problems below.\n\n== Sample Problems==\n\nThis ACSL category focuses on mathematical recursive functions rather than programming procedures; but you\u2019ll see some of the latter.\nYou will  typically  be asked to evaluate a recursive function for some specific value.   \nIt's important that you are careful and neat.  Work  your  way  down  the  recursive  calls  until  there  are  no  more  calls,  and  then  work  your  way  back  up.  \n \n=== Sample Problem 1 ===\n\n'''Problem:''' Find $g(11)$ given the following \n$$g(x)=\\cases\n{g(x-3)+1 & if $x>0$\\cr\n3x & otherwise\\cr\n}$$\n\n'''Solution:'''\n\nThe evaluation proceeds top-down as follows:\n\n$$\\begin{align}\ng(11)&=g(8)+1\\cr\ng(8)&=g(5)+1\\cr\ng(5)&=g(2)+1\\cr\ng(2)&=g(-1)+1\\cr\ng(-1)&=-3\\cr\n\\end{align}$$\n\nWe now use what we know about $g(-1)$ to learn more values, working our way back \"up\" the recursion:\n:We now know the value of $g(2): g(2)=-3+1=-2$\n:We now know the value of $g(5): g(5)= -2+1=-1$\n:We now know the value of $g(8): g(8) = -1+1=0$\n:And finally, we now have the value of $g(11): g(11)=0+1=1$\n\n=== Sample Problem 2 ===\n\n'''Problem:''' Find the value of $h(13)$ given the following definition of $h$:\n\n$$h(x)=\\cases\n{h(x-7)+1 & when $x>5$\\cr\nx & when $0 \\le x \\le 5$\\cr\nh(x+3) & when $x \\lt 0$}$$\n\n'''Solution:'''\n\n$$\\begin{align}\nh(13) &= h(6)+1 & \\text{top rule, since $x>5$}\\cr\nh(6) &= h(-1)+1 & \\text{top rule, since $x>5$}\\cr\nh(-1)&= h(-1+3) =h(2)& \\text{bottom rule, since $x<0$}\\cr\nh(2)&=2&\\text{middle rule, since $0 \\le x \\le 5$}\\cr\n\\end{align}$$\n\nWe now work our way back up the recursion, filling in values that have been computed.\n\n:$h(-1) = h(2) = 2$\n:$h(6)=h(-1)+1 = 2+1=3$\n:$h(13)=h(6)+1= 3+1=4$\n\n=== Sample Problem 3 ===\n\n'''Problem:''' Find the value of $f(12,6)$ given the following definition of $f$:\n\n$$f(x,y)=\\cases\n{f(x-y,y-1)+2 & when $x>y$\\cr\nx+y & otherwise}$$\n\n'''Solution:'''\n\n$$\\begin{align}\nf(12,6) &= f(6,5)+2 & \\text{top rule, since $x>y$}\\cr\nf(6,5) &= f(1,4)+2 & \\text{top rule, since $x>y$}\\cr\nf(1,4) &= 1+4 = 5& \\text{bottom rule, since $x \\le y$}\\cr\n\\end{align}$$\n\nWe now work our way back up the recursion, filling in values that have been computed.\n\n:$f(12,6) = f(6,5) + 2 = f(1,4) + 2 + 2 = 5 + 2 + 2 = 9$\n\n=== Sample Problem 4 ===\n\n'''Problem:''' Consider the following recursive algorithm for painting a square:\n\n1. Given a square.\n2. If the length of a side is less than 2 feet, then stop.\n3. Divide the square into 4 equal size squares (i.e., draw a \u201cplus\u201d sign inside the square).\n4. Paint one of these 4 small squares.\n5. Repeat this procedure (start at step 1) for each of the 3 unpainted squares.\n\nIf this algorithm is applied to a square with a side of 16 feet (having a total area of 256 sq. feet), how many square feet will be painted?\n\n'''Solution:'''\n\nIn the first pass, we get four squares of side 8.\nOne is painted, three are unpainted.\nNext, we have 3*4 squares of side 4.\nThree are painted (area=3*4<sup>2</sup>), nine are not.\nNext, we have 9*4 squares of side 2.\nNine are painted (area = 9*2<sup>2</sup>), 27 are not.\nFinally, we have 27*4 squares of side 1.\nTwenty-seven are painted.\nTherefore, the total painted is 1*8<sup>2</sup> + 3*4<sup>2</sup> + 9*2<sup>2</sup> + 27*1<sup>2</sup> = 175.\n\n== Online Resources ==\n\n===ACSL===\n\nThe following videos show the solution to problems that have appeared in previous ACSL contests. \n\n{|\n|-\n| <youtube width=\"300\" height=\"180\">https://youtu.be/YinptBVZNFM</youtube>\n| [https://youtu.be/YinptBVZNFM \"ACSL Math: Recursive Functions\" (Quick Coding Bytes)]\n\nThis video introduces the topic, then using an example problem, explains the methodology to solve problems that appear on ACSL contests.\n\n|-\n| <youtube width=\"300\" height=\"180\">https://youtu.be/OjZSIXStSr8</youtube>\n| [https://youtu.be/OjZSIXStSr8 ''Recursion Example 1'' ('''CalculusNguyenify''')]\n\nThe video walks through the solution to a straight-forward single-variable recursive function, that is, $f(x)=\\cases{....}$ \nThe problem\nappeared in ACSL Senior Division Contest #1, 2014-2015.\n\n|-\n| <youtube width=\"300\" height=\"180\">https://youtu.be/MWdGTVCLI8g</youtube>\n| [https://youtu.be/MWdGTVCLI8g ''Recursion Example 2'' ('''CalculusNguyenify''')]\n\nThe video walks through the solution to a 2-variable recursive function, that is, $f(x,y)=\\cases{....}$ . The problem\nappeared in ACSL Senior Division Contest #1, 2014-2015.\n\n|-\n| <youtube width=\"300\" height=\"180\">https://youtu.be/5P5iK-5heEc</youtube>\n| [https://youtu.be/5P5iK-5heEc ''Recursive Functions ACSL Example Problem'' ('''Tangerine Code''')]\n\nThe video walks through the solution to a 2-variable recursive function, that is, $f(x,y)=\\cases{....}$ . \n\n\n|}\n\n===Other Videos===\n\nBecause recursion is such a fundamental concept in computer science, there is no end to the number of YouTube videos that cover the topic. There are dozens of walk-throughs of the factorial and Fibonacci functions, and of other classic algorithms such as Towers of Hanoi and Binary Trees.\nSome of the videos contain ads; ACSL is not responsible for the ads and does not receive compensation in any form for those ads.\n\n{|\n\n|-\n| <youtube width=\"300\" height=\"180\">https://youtu.be/LdNdfPhwCP4</youtube>\n| [https://youtu.be/LdNdfPhwCP4 ''Recursion lecture 1'' ('''anim aland''')]\n\nProf. Alan Dorin from Monash University presents an wonderful introduction to recursion. The last part of the video uses factorial as an example. Taken note how his base case guards against infinite recursion.\n\n|-\n| <youtube width=\"300\" height=\"180\">https://youtu.be/dxyYP3BSdcQ</youtube>\n| [https://youtu.be/dxyYP3BSdcQ ''Fibonacci Sequence - Anatomy of recursion and space complexity analysis'' ('''mycodeschool''')]\n\nThe video is hand-simulation on the whiteboard of the recursive code for computing a Fibonnaci number. The code uses a base case of <syntaxhighlight lang=\"python\" inline>if n<=1 return n</syntaxhighlight> to prevent infinite recursion where the function called with a negative parameter.\n\n \n|}"
                    }
                ]
            },
            "3": {
                "pageid": 3,
                "ns": 0,
                "title": "Tests - Math",
                "revisions": [
                    {
                        "contentformat": "text/x-wiki",
                        "contentmodel": "wikitext",
                        "*": ";TeX Samples\n;TeX \uc0d8\ud50c\n\n== nowiki Test==\n<source lang='html5'>\n<math>E=mc^2</math>\n</source>\n<math>E=mc^2</math>\n\n<source lang='html5'>\n<nowiki><math>E=mc^2</math></nowiki>\n</source>\n<nowiki><math>E=mc^2</math></nowiki>\n\n== Inequality Sign Test ==\n<source lang='html5'>\n<math>1<2</math>\n</source>\n<math>1<2</math>\n\n<source lang='html5'>\n<math>2>1</math>\n</source>\n<math>2>1</math>\n\n<source lang='html5'>\n<math>1\\lt 2</math>\n</source>\n<math>1\\lt 2</math>\n\n<source lang='html5'>\n<math>2\\gt 1</math>\n</source>\n<math>2\\gt 1</math>\n\n== Inequality Sign Test 2 ==\n<source lang='html5'>\n<math>a<b</math>\n</source>\n<math>a<b</math>\n\n<source lang='html5'>\n<math>a < b</math>\n</source>\n<math>a < b</math>\n\n<source lang='html5'>\n<math>a>b</math>\n</source>\n<math>a>b</math>\n\n<source lang='html5'>\n<math>a > b</math>\n</source>\n<math>a > b</math>\n\n== UTF-8 Test ==\n<source lang='html5'>\n<math>\uc804\uc555 = \uc804\ub958 \\times \uc800\ud56d</math>\n</source>\n<math>\uc804\uc555 = \uc804\ub958 \\times \uc800\ud56d</math>\n\n<source lang='html5'>\n<math>\uc800\ud56d = \\frac{\uc804\uc555}{\uc804\ub958}</math>\n</source>\n<math>\uc800\ud56d = \\frac{\uc804\uc555}{\uc804\ub958}</math>\n\n<source lang='html5'>\n<math>\u511f\u9084\u307e\u3067\u306e\u5408\u8a08\u5229\u56de\u308a =\\left(1+\\frac{\u671f\u9593\u5229\u7387}{100}\\right)^{\u671f\u9593}</math>\n</source>\n<math>\u511f\u9084\u307e\u3067\u306e\u5408\u8a08\u5229\u56de\u308a =\\left(1+\\frac{\u671f\u9593\u5229\u7387}{100}\\right)^{\u671f\u9593}</math>\n\n<source lang='html5'>\n<math>n</math>\uac1c\uc758 \ub3d9\uc804\uc744 \ub358\uc838 \uc55e\uba74 <math>k</math>\uac00 \ub098\uc62c \ud655\ub960 <math>P(E)</math>\ub294?\n</source>\n<math>n</math>\uac1c\uc758 \ub3d9\uc804\uc744 \ub358\uc838 \uc55e\uba74 <math>k</math>\uac00 \ub098\uc62c \ud655\ub960 <math>P(E)</math>\ub294?\n\n== The Lorenz Equations ==\n<source lang='html5'>\n<math>\\begin{align}\n\\dot{x} & = \\sigma(y-x) \\\\\n\\dot{y} & = \\rho x - y - xz \\\\\n\\dot{z} & = -\\beta z + xy\n\\end{align}</math>\n</source>\n\n<math>\\begin{align}\n\\dot{x} & = \\sigma(y-x) \\\\\n\\dot{y} & = \\rho x - y - xz \\\\\n\\dot{z} & = -\\beta z + xy\n\\end{align}</math>\n\n== The Cauchy-Schwarz Inequality ==\n<source lang='html5'>\n<math>\\left( \\sum_{k=1}^n a_k b_k \\right)^2 \\leq \\left( \\sum_{k=1}^n a_k^2 \\right) \\left( \\sum_{k=1}^n b_k^2 \\right)</math>\n</source>\n<math>\\left( \\sum_{k=1}^n a_k b_k \\right)^2 \\leq \\left( \\sum_{k=1}^n a_k^2 \\right) \\left( \\sum_{k=1}^n b_k^2 \\right)</math>\n\n== A Cross Product Formula ==\n<source lang='html5'>\n<math>\\mathbf{V}_1 \\times \\mathbf{V}_2 =  \\begin{vmatrix}\n\\mathbf{i} & \\mathbf{j} & \\mathbf{k} \\\\\n\\frac{\\partial X}{\\partial u} & \\frac{\\partial Y}{\\partial u} & 0 \\\\\n\\frac{\\partial X}{\\partial v} & \\frac{\\partial Y}{\\partial v} & 0\n\\end{vmatrix}</math>\n</source>\n\n<math>\\mathbf{V}_1 \\times \\mathbf{V}_2 =  \\begin{vmatrix}\n\\mathbf{i} & \\mathbf{j} & \\mathbf{k} \\\\\n\\frac{\\partial X}{\\partial u} & \\frac{\\partial Y}{\\partial u} & 0 \\\\\n\\frac{\\partial X}{\\partial v} & \\frac{\\partial Y}{\\partial v} & 0\n\\end{vmatrix}</math>\n\n== The probability of getting k heads when flipping n coins is ==\n<source lang='html5'>\n<math>P(E)   = {n \\choose k} p^k (1-p)^{ n-k}</math>\n</source>\n\n<math>P(E)   = {n \\choose k} p^k (1-p)^{ n-k}</math>\n\n== An Identity of Ramanujan ==\n<source lang='html5'>\n<math>\\frac{1}{\\Bigl(\\sqrt{\\phi \\sqrt{5}}-\\phi\\Bigr) e^{\\frac25 \\pi}} =\n1+\\frac{e^{-2\\pi}} {1+\\frac{e^{-4\\pi}} {1+\\frac{e^{-6\\pi}}\n{1+\\frac{e^{-8\\pi}} {1+\\ldots} } } }</math>\n</source>\n\n<math>\\frac{1}{\\Bigl(\\sqrt{\\phi \\sqrt{5}}-\\phi\\Bigr) e^{\\frac25 \\pi}} =\n1+\\frac{e^{-2\\pi}} {1+\\frac{e^{-4\\pi}} {1+\\frac{e^{-6\\pi}}\n{1+\\frac{e^{-8\\pi}} {1+\\ldots} } } }</math>\n\n== A Rogers-Ramanujan Identity ==\n<source lang='html5'>\n<math>1 + \\frac{q^2}{(1-q)} + \\frac{q^6}{(1-q)(1-q^2)} + \\cdots\n= \\prod_{j=0}^{\\infty}\\frac{1}{(1-q^{5j+2})(1-q^{5j+3})},\n\\quad\\quad for\\,|q|<1.</math>\n</source>\n\n<math>1 + \\frac{q^2}{(1-q)} + \\frac{q^6}{(1-q)(1-q^2)} + \\cdots\n= \\prod_{j=0}^{\\infty}\\frac{1}{(1-q^{5j+2})(1-q^{5j+3})},\n\\quad\\quad for\\,|q|<1.</math>\n\n== Maxwell\u2019s Equations ==\n<source lang='html5'>\n<math>\\begin{align}\n\\nabla \\times \\vec{\\mathbf{B}} -\\, \\frac1c\\, \\frac{\\partial\\vec{\\mathbf{E}}}{\\partial t} & = \\frac{4\\pi}{c}\\vec{\\mathbf{j}} \\\\   \\nabla \\cdot \\vec{\\mathbf{E}} & = 4 \\pi \\rho \\\\\n\\nabla \\times \\vec{\\mathbf{E}}\\, +\\, \\frac1c\\, \\frac{\\partial\\vec{\\mathbf{B}}}{\\partial t} & = \\vec{\\mathbf{0}} \\\\\n\\nabla \\cdot \\vec{\\mathbf{B}} & = 0\n\\end{align}</math>\n</source>\n\n<math>\\begin{align}\n\\nabla \\times \\vec{\\mathbf{B}} -\\, \\frac1c\\, \\frac{\\partial\\vec{\\mathbf{E}}}{\\partial t} & = \\frac{4\\pi}{c}\\vec{\\mathbf{j}} \\\\   \\nabla \\cdot \\vec{\\mathbf{E}} & = 4 \\pi \\rho \\\\\n\\nabla \\times \\vec{\\mathbf{E}}\\, +\\, \\frac1c\\, \\frac{\\partial\\vec{\\mathbf{B}}}{\\partial t} & = \\vec{\\mathbf{0}} \\\\\n\\nabla \\cdot \\vec{\\mathbf{B}} & = 0\n\\end{align}</math>\n\n==\uac19\uc774 \ubcf4\uae30==\n*[[TeX]]\n\n==\ucc38\uace0 \uc790\ub8cc==\n*https://www.mediawiki.org/wiki/Extension:SimpleMathJax\n*http://www.mathjax.org/demos/tex-samples/"
                    }
                ]
            }
        }
    }
}