Recursion

Question

Can someone explain it in simple terms? And how it is completed in Python?

I am trying to create an ABACABA generator.

I understand iteration, but not recursion.

Thankss

Answer 1

See the reference down below:
https://www.sololearn.com/discuss/307407/?ref=app
https://www.sololearn.com/discuss/1294343/?ref=app

Answer 2

Robin such a great explanation! 👍

Recursion is wonderful, and too bad that most of the mainstream languages don't have sufficient support for it, making it very dangerous to use, as memory overflow can occur. I really started to understand and appreciate it after learning functional languages like Haskell and Clojure.
Thinking about recursion can really blow the mind.. For me it usually helps to nail down the base case first: when the function doesn't need to do anything. Then build the next step from there.. And due to the nature of recursion, the rest is sort of automatic :)

https://code.sololearn.com/cjwPBaUb72b5/?ref=app
https://code.sololearn.com/cKu15Wn8y19d/?ref=app
https://code.sololearn.com/cZ9exzN9P7jw/?ref=app

Answer 3

From concept Rekursion is, if a function call itself.
Its like in RL.
If you dont know the way to pizza, you could use the method function "ask for the way". If the result != "Here turn around & look, its here!", you could use this method again.

I do a example in code. Read it carefuly, I hope it help.

# -------
# way to the club example

# requiered import
from random import choice as ch

# list of directions
directions = [
"go right and follow the street",
"go left and follow the street",
"go straight and follow the street",
"turn around its here!"
]

# function which call itself

def ask_for_way(argument1):
direction = ch(directions)
if argument1 == "turn around its here!":
quit()

else:
print(direction)
ask_for_way(direction)

ask_for_way("no idea")

# EOF

Answer 4

【１】

► Preamble:

First, I'd like to thank @Robin for such devotion for gathering his thoughts and wisdom to draft such an informative article (considering the formatting and text length limitations here) for leading a new learner and demystifying the subject.

► OP's frustration is understandable:

"I hate recursion!"
"Math is so crazy sometimes[...]"

► A very simple example

We are asked to formulate a recursive solution for the following statement. But before that, it also needs us to prove that the summation on the left side is equal to the right side of the equation

S(n) = Σ [j = 0 to n] 2ʲ = 2ⁿ⁺¹ - 1, for all n ≥ 0

It reads "the sum of the powers of 2 between 0 and n is equal to 1 less than (n+1)st power of 2". that is,

2⁰ + 2¹ + 2² + ... + 2ⁿ = 2ⁿ⁺¹ - 1

If n = 3, then

2⁰ + 2¹ + 2² + 2³ = 2³⁺¹ - 1 = 15

(Inductive part of the deal)
As mentioned earlier, recursion and induction are inseparable. In fact, recursion is a technique for simulating mathematical induction in a programming language. To that end, we need to learn how mathematical induction works and what steps require for devising a successful solution to a given problem, even though all that effort is merely for showing us the correctness of the solution (you'd go for trial and error instead).

(Proof)
■ Basis: Since 0 is our lower bound, we set it as the base case S(0). In other words

S(0) = 2⁰ = 2¹ - 1 = 1

We just showed the n = 0 is true.

■ Inductive steps: Now we can convince ourselves that every substitution of (j) up to (n) yields true. If n=3 is true, does n=4 also true, or n = 1000? To see what happen to the next n, (n+1), let's replace n in the above statement with n+1

Σ [j = 0 to (n+1)] 2ʲ = 2ⁿ⁺² - 1

The left side of the above sum is identical to Σ [j = 0 to n] 2ʲ plus j = n+1. So, we break it up as

Σ [j = 0 to (n+1)] 2ʲ = ( Σ [j = 0 to n] 2ʲ ) + 2ⁿ⁺¹

Substituting the right side, 2ⁿ⁺¹ - 1, for what is inside the parentheses we get

[continue]

Answer 5

【２】

Σ [j = 0 to (n+1)] 2ʲ = ( 2ⁿ⁺¹ - 1 ) + 2ⁿ⁺¹

By simplifying the right side we have

Σ [j = 0 to (n+1)] 2ʲ = 2 * 2ⁿ⁺¹ -1

∴ Σ [j = 0 to (n+1)] 2ʲ = 2ⁿ⁺² -1

Which is the same equation we wanted to prove for (n+1) and it's valid for every nonnegative n.

► Recursive algorithm:

Sum-Powers-Two ( n )
If n == 0
return 1
else
return ( Nth-Power-Two ( n ) + Sum-Powers-Two ( n-1 ) )

Nth-Power-Two ( m )
if m == 1
return 2
else
return ( 2 * Nth-Power-Two ( m-1 ) )

Answer 6

actually, its a little scary

Answer 7

@Robin

from collections import OrderedDict

a = int(input())

def abacaba(b):
y = []
g = []
c = OrderedDict()
q = (b * 2)-1
for x in range(1, 27):
c[x] = str(chr(96+x)).upper()
o = 0
for l in range(len(y), 0, -1):
g.append(c[b - o])
o = o +1
print(g)

abacaba(a)

Sorry for being so immature, recursion is scary but it happens in nature. Anyway, this is my code. I'm still working on it. ;/

Answer 8

I had nightmares and literally dreamed in code. But I thank you. I’ll have to see what declarative & imperative means. But your posts clarified, to me, what it could but a lot I dont understand. I will come back to it. And maybe experience will help. Math is so crazy sometimes, and youd think it would be logical but at times... TOO logical for the human mind. 🤯 Thank you Robin so much

Answer 9

Hmm... thats a recursive definition. 🤦‍♀️

Answer 10

poor Robin, please dont let it consume you. i wish i could help 🥺

Answer 11

I hate recursion!

Answer 12

Just to let ya’ll know, I am taking a break from coding for a little bit to clear my mind. I like coding, but my brain needs to rest. I hope to be a better program after this mind vacay. Thanks for trying to help me understand such a strange, exciting and horrible process that is ~recursion<< Best regards, Mad 💜