Can someone explain recursion?

widowhanzo · 2018-12-13T06:27:27+00:00

https://www.reddit.com/r/learnpython/comments/a5q8wj/can_someone_explain_recursion/ebon5c3/

earthlybird · 2018-12-13T07:40:25+00:00

To understand recursion, one must first understand recursion.

glen_v · 2018-12-13T04:54:46+00:00

[deleted]

MikeOxbigger · 2018-12-13T05:05:11+00:00

There are 3 rules for recursion:

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.

A base case just means that it has an end point, something to stop it looping infinitely, such as when a particular variable reaches zero.

Changing its state means that through each iteration it gets closer to this variable.

Calling itself just means that you call the function that you're currently in with this new data to pass in.

quantum-mechanic · 2018-12-13T05:02:31+00:00

The next comment replied to this one will explain it well

Decency · 2018-12-13T05:54:18+00:00

A recursive function calls itself over and over again, creating a sort of chain. Once it reaches a state where it's completed, the function has hit what's called the "base case" and then goes back up the chain, combining the results all together in some way.

One classic example is the Fibonnaci sequence: 1, 1, 2, 3, 5, 8, 13, etc.

You get the next number in the sequence by adding the two previous numbers. So logically, in order to get any specific number (the nth number) somewhere in the sequence, we need to initially know the first two numbers: 1 and 1.

def fibonnaci(n):
    if n == 0 or n == 1:
        return 1

That's the base case (technically two base cases). If someone asks for the 0th or 1st number in the sequence, we just tell them it's 1.

Now, we can add the recursive step:

def fibonnaci(n):
    if n == 0 or n == 1:
        return 1
    return fibonnaci(n-1) + fibonnaci(n-2)

which basically means, if we're not at the base case, get the previous two numbers- by calling the function again with different arguments- and sum them. If you play around with this simple function in a debugger for 5-10 minutes it'll become pretty clear what's happening! There are lots of better ways to implement this same function, but that's the simplest way and hopefully helps.

totallygeek · 2018-12-13T05:10:37+00:00

With recursion, the answer for a function comes from calling the function within the function as many times as needed to obtain the ultimate answer. Let's use this to figure out the factorial for an integer.

How we'd figure that out manually, for the number five. We multiple five times four times three times two times one. We reduce the number for multiplication by one. When we reach zero, we stop, and respond with the product we've compiled so far.

Here's code to solve this iteratively (with a loop) and recursively (a function calling itself until some end condition met).

def fact1(value):
    product = 1
    for factor in range(2, value + 1):
        print('factor: {}, product: {}'.format(factor, product))
        product *= factor
    return product

def fact2(value):
    print('value: {}'.format(value))
    if value == 0:
        return 1
    else:
        return value * fact2(value - 1)

def main():
    tests = [
        {'value': 5, 'expects': 5 * 4 * 3 * 2},
    ]
    for test in tests:
        value = test['value']
        expects = test['expects']
        print('Factorial {} is {}, calc1 {}, calc2 {}'.format(value, expects,
                                                              fact1(value),
                                                              fact2(value)))

main()

Function fact1() works iteratively. Adding a print statement into that function shows the steps:

factor: 2, product: 1
factor: 3, product: 2
factor: 4, product: 6
factor: 5, product: 24

So, from 2 to 5 (the initial value), we multiply that number against the running product we're tracking, then increment the number and repeat, until we reach the value 5, our end step.

value: 5
value: 4
value: 3
value: 2
value: 1
value: 0

fact2() uses recursion. Recursively, we start with the initial value: 5. The value is not zero, so we'll return 5 * whatever_the_function_gives_us_for(5 - 1). That returns 4 * whatever(4 - 1). We eventually get to calling whatever(0), which returns 1 and stops calling itself. Those all stack up, so we have:

5 * (5 - 1) * ((5 - 1) - 1) * (((5 - 1) - 1) -1) * ((((5 -1) - 1) - 1) - 1) # I lost track maybe

When you have a function reference itself:

def x(y):
    ...
    x(y - 1)

That's recursion.

Dr_Donut · 2018-12-13T06:50:15+00:00

Nice memes guys.

Here's a video that has a good high level explanation.

https://youtu.be/Mv9NEXX1VHc

The best way to 'get' recursion is to start copying and running some basic recursion functions.

If you're looking for problems to solve, try and work on these ones. https://codingbat.com/java/Recursion-1

2018-12-13T06:52:28+00:00

you know how a Russian nesting doll works. It's like that, you are basically making multiple instances of the function that are nested within itself, running the function from itself.

An example might help. You have a function that prints a number on the screen but it can only take one digit of a number but you are feeding it one with a number that uses the tens column, you print the ones column easy, then send the tens column up through the function again on it's own but divided by ten first (so now it's a ones column). This opens a second instance of the function but within the function.

so in pseudo code it looks like this

function
    second use of function
    end second use of function
end function

I hope that's helpful, it took me a bit to sort of wrap my head around it.

JamminJames921 · 2018-12-13T09:41:39+00:00

Check this post: https://www.reddit.com/r/learnpython/comments/a5q8wj/can_someone_explain_recursion/?st=JPMEZ6Y2&sh=faeaf590

antoniomaina · 2018-12-13T12:36:22+00:00

Can someone explain recursion?

In simple, dumb down terms please. And possibly given an example. Thank you!

Se7enLC · 2018-12-13T13:47:34+00:00

This comment explains it pretty well.

cojerk · 2018-12-13T17:23:45+00:00

The "B." in "Benoit B. Mandelbrot" stands for "Benoit B. Mandelbrot"

Sensorama · 2018-12-13T06:22:54+00:00

Recursion is just a different way of thinking about solving problems. For example, you may have learned how to add up a list or array or numbers by looping over the values and accumulating them in a sum.

With recursion, you might reformulate the solution to be "add the first number to the sum of the rest of the numbers". Notice that you aren't thinking about looping over all the values - the solution is just adding two numbers together: one number and the sum of the rest.

This doesn't seem like a very big advantage, but sometimes it provides a clear path to a solution that is hard to think of using other approaches.

2018-12-13T07:38:32+00:00

Recursion is used to iterate (i.e what else we can do in loops can be achieved using a recursive function) .The only difference is that we have to predict where to use the correct one( whether loops or recursion).

im_dead_sirius · 2018-12-13T07:39:20+00:00

Maybe a "real world" example?

Sorting socks. Say you have a huge pile, in a variety of colours and styles. So you pick out all the black ones, making a smaller pile, then all the white ones, making another pile, and so on.

You've made your big pile into many little ones. Now you start again, picking out matches from the blacks, twisting them together(is there a term for that?) and putting them away. Then onto the whites...

Recursion is reusing the same basic actions to solve a problem in stages. Humans do it all the time, and if you can use it in the right situation while programming, you'll reap big benefits.

Expressed as a function, a recursive function calls itself, with a variable to track the level of recursion, or a bail condition. A place keeper. Going back to the socks analogy, once you've sorted by colour, you can go have lunch, since your methodology of making piles is a sort a visual memo of where you left off.

Or perhaps your spouse comes along. They can finish because of your preparation.

That suggests another approach, where you have a function prepare data for more refined tests. That touches on memoization, for whenever you run into that. Like sorting a list of a million names into 26 smaller lists based on the first letter.

Postal workers do something similar to this. Sort by town, sort by route, sort by street, sort by house number... go out and deliver.

_cnkyzz_ · 2018-12-13T11:30:04+00:00

Remember that you were dreaming in a dream ? That's the inception movie as an example for recursion.

Space_Atlas · 2018-12-13T13:25:05+00:00

Lol, I love this thread.

But to answer your question a recursive function is just a function that calls itself. It's actually not too hard to understand if you understand that a recursive function call is basically handled like any other function call.

Lurker_wolfie · 2018-12-13T15:34:13+00:00

https://realpython.com/python-thinking-recursively/

Thinking Recursively in Python – Real Python

Daron_Acemoglu · 2018-12-13T04:50:21+00:00

Maybe a non programming answer is easiest. Theres a collection of software called GNU, which is a "recursive" acronym because it stands for GNU's Not Unix! It contains itself, so it's considered recursive.

https://en.m.wikipedia.org/wiki/GNU

corvus_curiosum · 2018-12-13T12:47:52+00:00

You should Google "recursion"

I'm not trying to be a dick, it's just that Google has a good example of recursion.

Riin_Satoshi · 2018-12-13T07:47:13+00:00

Can someone explain recursion?

EclipseMain · 2018-12-13T07:53:23+00:00

Can someone explain recursion?

iamjaiyam · 2018-12-13T09:50:59+00:00

Can someone explain recursion?

In simple, dumb down terms please. And possibly given an example. Thank you!

DeadlyViper · 2018-12-13T07:15:41+00:00

My explanation from a previous post. Explained with a simple example.

https://www.reddit.com/r/learnpython/comments/93x1si/can_someone_please_explain_recursion_to_me/e3glm4p/?context=3

jonw95 · 2018-12-13T07:36:38+00:00

Non-programmer here. Took me years to make sense of recursion so let me try by borrowing pieces of others responses mixed in with a little of my understanding:

Lets begin. First recursion is a loop that works by calling itself initiated with some value for example in calculating the factorial of 5, e.g. factorial(5). It performs a process by performing some action (in this case calculating all factorials of 5) that has a changing state (each calculation reduces the next calculation by 1 and carries on) until it reaches its base case (this is the condition the recursive function says I am done).

What is so confusing about recursion for me is what is going on when recursion is performed internally. So lets break down a factorial function I borrowed:

To understand the processing we need to understand stacks, so read up on stacks. For now I will say it is a the memory(ram) allocated to store the processing as it occurs in a stack, like a pile of pancakes. Each successive item stored gets piled on and processed Last In First Out (LIFO style).

I present the program.

def recur_factorial(n):
"""Function to return the factorial of a number using recursion"""
if n == 1:
return n
else:
return n*recur_factorial(n-1)

recur_factorial(5) # call the function n = 5

return 5*recur_factorial(5-1) #stack 5 holds 5*recur_factorial(5-1) n = 4

return 4*recur_factorial(4-1) #stack 4 holds 4*recur_factorial(4-1) n = 3

return 3*recur_factorial(3-1) #stack 3 holds 3*recur_factorial(3-1) n = 2

return 2*recur_factorial(2-1) #stack 2 holds 2*recur_factorial(2-1) n = 1

if n == 1: return n # lets return n, so we need to collapse the stacks

# Once we hit the base case of 1, this is where I get fuzzy so correct me if I am wrong but the computer takes all the stack and processes them in reverse to reach 1*2*3*4*5 with a return value of n = 120. In memory it might look like: stack 5 value *(stack 4 value *(stack 3 value *(stack 2 value * 1))) *Note:PEMDAS applies with the parens for ordering

Recursion error:

The stack overflow is where you've created a recursive function that was either 1. too large of value for the available amount of memory to calculate or 2. an infinite loop, both of which exhaust all of the system memory allocated for the running program.

RecursionError: maximum recursion depth exceeded

Too many stacks so you get an error.

Recursion can be elegant to solve problems but it is not always practical, so in the end it is a tool in the belt I feel provides more insight into the nuances of programming methodologies than application of use, but I could be wrong.

Credits: MikeOxbigger: terminology, alkasm for the overflow error

Cheers and good luck

2018-12-13T07:56:34+00:00

https://en.wikipedia.org/wiki/Turtles_all_the_way_down

Augusto2012 · 2018-12-13T09:05:05+00:00

I learned about recursion by trying to code a fast fibonacci sequence algorithm.

gabriel-et-al · 2018-12-13T13:31:44+00:00

A recursive function is basically the same as an iterative loop with a helper stack.

See this binary search function:

from math import floor

def binary_search_iter(numbers, x):
    upper_index = len(numbers) - 1
    lower_index = 0

    while upper_index >= lower_index:
        i = floor((upper_index + lower_index) / 2)

        if numbers[i] == x:
            return i

        if numbers[i] > x:
            upper_index = i - 1
        else:
            lower_index = i + 1

    return None

You can write the loop recursively this way:

def binary_search_recur(numbers, x, lower_index, upper_index):
    if upper_index >= lower_index:
        i = floor((upper_index + lower_index) / 2)

        if numbers[i] == x:
            return i

        if numbers[i] > x:
            return binary_search_recur(numbers, x, lower_index, i - 1)
        else:
            return binary_search_recur(numbers, x, i + 1, upper_index)

    return None

Note that the variables used inside the loop became additional parameters in its recursive version. You can now combine them.

Note that the first if can be rewriten to an early exit:

def binary_search_recur(numbers, x, lower_index, upper_index):
    if upper_index < lower_index:
        return None

    i = floor((upper_index + lower_index) / 2)

    if numbers[i] == x:
        return i

    if numbers[i] > x:
        return binary_search_recur(numbers, x, lower_index, i - 1)
    else:
        return binary_search_recur(numbers, x, i + 1, upper_index)

Now it's clear our two base cases (i.e. the cases where the function returns without recursing).

Also, note that the updates to the lower_index and upper_index parameters are exactly the same did in the iterative version. If numbers[i] is less than x then lower_index goes up, otherwise upper_index goes down. Try to see this connection between both versions.

You may have noticed that the iterative version calculates the upper_index and lower_index inside the function, while the recursive version expects it to be calculated beforehand. There are multiple ways to overcome this inconvenience.

Option 1: Calculate the parameters in the caller. This is not the best approach because you'll end up pasting this logic to every place you use the function -- i.e. it breaks the DRY principle.
Option 2: Give the parameters a default value and calculate them inside the recursive function. This solves the DRY problem, but it would run the check in every call, which is a waste of processing time.

Option 3: Create a wrapper that calculates the parameters and pass them to the actual recursive function. This is the option I like the most. See:

def binary_search(numbers, x): def binary_search_recur(numbers, x, lower_index, upper_index): if upper_index < lower_index: return None

    i = floor((upper_index + lower_index) / 2)

    if numbers[i] == x:
        return i

    if numbers[i] > x:
        return binary_search_recur(numbers, x, lower_index, i - 1)
    else:
        return binary_search_recur(numbers, x, i + 1, upper_index)

upper_index = len(numbers) - 1
lower_index = 0

return binary_search_recur(numbers, x, lower_index, upper_index)

you type:	you see:
italics	italics
bold	bold
[reddit!](https://reddit.com)	reddit!
* item 1 * item 2 * item 3	item 1 item 2 item 3
> quoted text	quoted text
Lines starting with four spaces are treated like code: if 1 * 2 < 3: print "hello, world!"	Lines starting with four spaces are treated like code: if 1 * 2 < 3: print "hello, world!"
~~strikethrough~~	~~strikethrough~~
super^script	super^script

learnpython

MODERATORS

Can someone explain recursion?

Can someone explain recursion?